排序算法是最常用的一种算法，在面试中也会经常被问到，今天以升序为例总结一下集中常用的排序算法，以及复杂度和稳定性。
关于稳定性：稳定性指的是一组数据中如果存在相等的数据，Ai=Aj，排序前Ai在Aj的前面，那么排序后Ai仍然在Aj的前面，那么这种排序算法就是稳定的，反正则是不稳定的。
常见的排序算法有：
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 堆排序
希尔排序
冒泡排序
排序思想：冒泡排序的核心思想就是比较相邻两个变量的大小，然后将不符合顺序的两个变量交换位置。如果有n个变量，则需要n-1趟比较，第一趟比较将最大值排序到倒数第一的位置，第二趟排序将次大值排序到倒数第二的位置……直到第n-1趟比较，可以将所有的变量都回归到正确的位置。时间复杂度为O(n^2)。很显然，冒泡排序是一种稳定的排序算法。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14void bubble_sort(int* &a,int n)
{
int i,j,temp;
for(i=n-1;i>0;i--)
{
for(j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);// swap函数交换位置
}
}
}
}
选择排序
- 排序思想：顾名思义，选择排序就是将n个元素中最小的一个挑选出来放在第0号位置，然后将剩下的n-1个元素中挑选最小的元素放在第
1号位置……经过n-1次挑选，可以将全部的元素回归到正确的位置。时间复杂度为O(n^2)。选择排序是一种不稳定排序算法，每次交换位置，都有可能会打乱原来元素的相对位置，所以是一种不稳定的算法。代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void selection_sort(int* &a,int n)
{
int i,j,pos,temp;
for(i=0;i<n-1;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[pos])
{
pos=j;
}
}
swap(a[pos],a[i]);// swap函数交换位置
}
}
插入排序
排序思想：有排序完毕的一组数据a1,a2,……av，现在将第v+1个数据，插入到这组有序的数据中，需要找到第一个小于或等于a[v+1]的数，插入到其后。如果有n个元素，则需要进行n-1次插入操作，每次插入操作都不会打乱原来相等元素的相对位置，所以插入排序是稳定算法。时间复杂度为O(n^2)。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13void insert_sort(int* &a,int n)
{
int i,j,v;
for(i=1;i<n;i++)
{
v=a[i];
for(j=i-1;j>=0 && a[j]>v;j--)
{
a[j+1]=a[j];// 如果v的值小于a[j]的值，则将a[j]的值向后移动
}
a[j+1]=v; //将a[i]的值放入第一个小于或者等于a[i]的后面一个位置
}
}
快速排序
- 排序思想：假设有n个元素的数组a[n]，选择一个基准元素，一般选取a[0]。设置左右遍历索引，low=0,high=n-1。先从右往左遍历，直到遇到第一个小于a[0]的元素，然后交换位置；然后从左往右遍历，直到遇到第一个大于a[0]的元素，然后交换位置。如果high的值小于或者等于low，则遍历结束。此时low位置将序列分为两个部分[0,low-1]和[low+1,n-1]，对这两个序列分别进行快速排序，即可得到排序结果。排序时间复杂度为O(n*logn)。是一个不稳定排序算法。代码如下：
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
26void Quick_sort(int* &a,int left,right)
{
if(left<right)
{
return;
}
int low=left;
int high=right;
int temp=a[low];
while(low<high)
{
while(high>low && a[high]=>temp)
{
high--；
}
swap(a[high],a[low]); //当high==low时，交换也没有影响，所以这里不需要判断，直接进行交换
while(low<high && a[low]<=temp)
{
low++;
}
swap(a[high],a[low]);
}
Quick_sort(a,left,low-1);
Quick_sort(a,low+1,right);
}
堆排序
- 排序思想：利用堆这种数据结构的特殊性，来进行排序。首先数组元素的小标索引应该从1开始，第i个节点左右子节点分别为i2和i2+1。首先自底向上建堆，然后取堆顶元素和最后一个元素进行交换，再对堆顶元素的位置进行调整。再去倒数第二个元素和堆顶元素进行交换，再次调整堆顶元素的位置，直到堆中只有一个数据为止。时间复杂度为O(n*logn)。代码如下：
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
36void downAdjust(int* &a,int low,int high)
{
int i=low,j=i*2;
while(j<=high)
{
if(j+1<=high && a[j+1]>a[j])
{
j=j+1;
}
if(a[i]<a[j])
{
swap(a[i],a[j]);
}
else
{
break;
}
}
}
void creatHeap(int* &a,int n)
{
for(int i=n/2;i>=1;i--)
{
downAdjust(i,n);
}
}
void heapSort(int* &a,n)
{
creatHeap(a,n);
for(int i=n;i>1;i--)
{
swap(a[i],a[1]);
downAdjust(1,i-1);
}
}
