7种排序算法

发表于 更新于 分类于

#冒泡排序

稳定排序
时间复杂度：需要比较\(\frac{(n-2+1)(n-2)}{2}\)次，\(O(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(int&a,int&b)
{
	a^=b;
	b^=a;
	a^=b;
}
void bubbleSort(int a[],int n)
{
	for (int i=0;i<n-1;++i)
	{
		for(int j=n-1;j>i;j--)
		{
			if(a[j]<a[j-1])
			{
				swap(a[j-1],a[j]);
			}
		}
	}
}

#选择排序

不稳定,2个相等的数据项可能排序后先后位置变化
\(O(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void selectSort(int a[],int n)
{
	for (int i=0;i<n-1;++i)
	{
		int k =i;
		for (int j=i+1;j<n;++j)//从剩下的元素中选出最小的
		{
			if(a[k]>a[j])
				k=j;//k指向最小元素的下标
		}
		if(i!=k)//注意swap的2个变量不能指向同一个元素，由于异或的使用
		swap(a[i],a[k]);
	}
}

#直接插入排序

稳定
\(O(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(int a[],int n)
{
	for (int i =0;i<n-1;++i)//
	{
		int temp = a[i+1];
		int j=i;
		for (;j>-1&&temp<a[j];--j)
		{
			a[j+1] = a[j];
		}
		a[j+1] = temp;
	}
}

#希尔排序

不稳定
\(O(n^{\approx1.2})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void shellSort(int a[],int n)
{
	for (int gap=n/2;gap>0;gap/=2)
	{
		for (int i=0;i<gap;++i)
		{
			for (int j=i;j<n-gap;j+=gap)//这里其实就是插入排序
			{
				int k=j;
				int temp=a[j+gap];
				for (;k>=0&&temp<a[k];k-=gap)
				{
					a[k+gap]=a[k];
				}
				a[k+gap] = temp;
			}
		}
	}
}

#归并排序

稳定
\(O(n*log_2n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void mergemerge(int a[],int l,int mid,int r,int temp[])
{
	int m=l,n=mid+1,k=0;
	for (;m<(mid+1)&&n<(r+1);)
	{
		if(a[m]<=a[n])
			temp[k++]=a[m++];
		else
			temp[k++]=a[n++];
	}
	for (;m<(mid+1);)
	{
		temp[k++]=a[m++];
	}
	for(;n<(r+1);)
	{
		temp[k++]=a[n++];
	}
	for(int i=0;i<k;i++)
	{
		a[l+i]=temp[i];
	}
}

void innerMergeSort(int a[],int l,int r,int temp[])
{
	if(l<r)
	{
		int mid=(l+r)/2;
		innerMergeSort(a,l,mid,temp);
		innerMergeSort(a,mid+1,r,temp);
		mergemerge(a,l,mid,r,temp);
	}
}
void mergeSort(int a[],int n)
{
	int *pt = new int[n];
	innerMergeSort(a,0,n-1,pt);
	delete[]pt;
}

#快速排序

不稳定
\(O(n*log_2n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void quickSort(int a[],int l,int r)
{
	if(l<r)
	{
		int i=l,j=r;
		int temp=a[i];//key value
		while(i<j)
		{
			for (;i<j&&temp<a[j];)
				--j;
			if(i<j)
			{
				a[i++]=a[j];
			}
			for(;i<j&&temp>a[i];)
				++i;
			if(i<j)
				a[j--]=a[i];
		}
		a[i]=temp;
		
		quickSort(a,l,i-1);//这里a[i]位置已经不要算进去了
		quickSort(a,i+1,r);
	}
}

#堆排序

不稳定
\(O(n*log_2n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//最小堆
void heapDown(int a[],int n,int i)//a数组，n个元素,调整的位置为i(注意这里i是从0开始的）
{
	int j=2*i+1;//左子节点
	int tmp = a[i];
	while(j<n) //这个过程其实基本就是插入排序的思想
	{
		
		if(j+1<n&&a[j+1]<a[j])
			j+=1;
		if(tmp<=a[j])
			break;
		a[i] = a[j];
		i=j;
		j=2*i+1;
	}
	a[i]=tmp;
}
void makeHeap(int a[],int n)//构造最小堆
{
	//这里的原理是，叶子节点只有一个元素是最小堆，
	//从最后一个父节点开始由下及上的把所有子树构造为最小堆
	for (int i=n/2-1;i>=0;i--)
	{
		heapDown(a,n,i);
	}
}

//最小堆对应的排序是降序
void heapSort(int a[],int n)
{
	makeHeap(a,n);
	for (int i=1;i<n;++i)
	{
		swap(a[0],a[n-i]);
		heapDown(a,n-i,0);
	}
}