排序算法可以说是数据结构与算法系列中的精华，常用的排序算法一般来说有十种，包括插入排序、选择排序、冒泡排序、梳排序、希尔排序、堆排序、快速排序、归并排序、基数排序以及计数排序。接下来，我将根据自己的理解对这10种排序算法进行简单的分析总结。为了统一，以下排序都遵循从小到大的原则。
-
插入排序
1.算法分析
插入排序排序其实跟后面的排序有些不一样，它是从数组创建的角度去考虑的，每一次对数组插入新的元素时都会对插入的元素进行评估，观察是否放在正确的位置。需要注意的是，对新插入元素进行评估并正确放置的前提是前面的元素已经全部正确放置。
举例来说，向一个数组a分别插入2,3,1，要求顺序是从小到大。最先向a[0]插入2，再向a[1]插入3时， 将3与2比较，顺序没有问题，再插入1，进行比较发现1比2还要小，因此要将2和3都往后移一位到a[1]与a[2]，再将1放到2原来的位置，也就是a[0]。
2.程序
void insertsort(int *data,int N)
{
for(int i=1;i<N;i++)
{
int T=data[i];//保存当前要插入的数据（实际上现在并不是在创建数组，而是在假想在将数据插入数组）
for(int j=i-1;j>=0;j--)//所有比待插入的数据大的数全都往后移一位
if(data[j]>data[i]) data[j+1]=data[j];
data[j]=T; //将待插入数据的数据放置到正确位置
}
}
3.复杂度与稳定分析：
首先是空间复杂度，显然整个排序过程并没有额外占用空间，因此空间复杂度是O(1)。再看时间复杂度。最优的情况下，自然是所有数据都已经排好了。这样的话，只需要比较N-1次（除第一个数据外，每个数据都与前面一个数据比较一次），最差的情况下是数据完全按相反的顺序排列，那么需要比较的次数是
，而需要移动（赋值）的次数是：
。平均情况下，比较复杂度是
,大概是最差情况下的一般，移动的复杂度同样。
稳定性方面显然如果两个数据相同，插入排序不会改变两者顺序，因此插入排序是稳定的。
-
选择排序
1.算法分析
选择排序的思想比较简单，就是依次找到最小的数，将其放在合适的位置上。举例来说，数组a[4]中有2,1，4,3四个元素，首先找到最小的元素1，将其与第一个元素2交换，然后在剩下的元素2,4,3中找到最小的数2，降低与第二个元素交换（实际上已经在正确的位置了），以此类推，直至所有元素都找到自己的位置。事实上，我们在将一个队伍按身高从低到高排序时就经常会利用这样的思想。
2.程序
void selectionsort(int *data,int N)
{
for(int i=0;i<N;i++)
{ for(int j=i+1,least=i;j<N;j++)
if(data[j]<data[least])
least=j;
swap(data[i],data[least]);
}
}
3.复杂度与稳定性分析
首先是空间复杂度，排序过程中并没有用到额外空间，因此空间复杂度是O(1)。时间复杂度方面，很显然，不管什么情况，赋值次数
（这是书上的说法，实际上这里好像只考虑了对元素的赋值，而忽略了元素下标的赋值，难道在找最小元素的过程中，least=j就不算赋值？所以我对这种说法保留意见），而如果想减少无用的赋值次数（例如数据本身已经在合适的位置上），可以对swap函数添加一个条件。而对于比较复杂度，很显然，不管顺序怎么样比较的复杂度都是
。
稳定性方面，如果遇到有相同的数，排在前面的数，会先找到自己的位置，因此选择排序也是稳定的。
-
冒泡排序
1、算法分析
冒泡排序实际上我觉得跟选择排序很相似，都是为了依次将最小的数据区别在于前者从数组尾开始操作，并且一直在进行元素交换，而后者是从数组头开始操作，并且在找到最小的元素之前，进行的仅仅是下标的赋值，只有等真正找到了最小的元素后，才进行元素的交换。
冒泡排序的过程就像其名字描述的那样形象，以数组a[4]={2,3,1,4}为例，首先是找到数组尾的a[3]=4，将其与前一个元素1比较，发现4>1，所以按兵不动，接下来将a[2]=1与a[1]=3 比较，发现1<3，因此将1与3交换，现在a[1]=1,再将a[1]=1与a[0]=2比较，发现1<2，于是交换两者，现在a[0]=1，也就是通过这样一个两两交换的过程，将最小的数浮到了最上层，就像一个气泡慢慢往上冒一样。剩下的的元素按照一样的操作就可以完成排序
2、程序
void bubbblesort(int *data,int N)
{
for(int i=N-1;i>0;i--)
for(int j=N-2;j>0;j--)
{
if(data[j]<data[j-1])
swap(data[j],data[j-1]);
}
}
3、复杂度以及稳定性分析
显然冒泡排序的空间复杂度为O(1)，时间复杂度方面，最好情况下是数据已经按顺序排列，这时只需要进行比较比较的复杂度为
，而最差情况下，比较复杂度与赋值复杂度均为
。平均情况下也是这样，不过复杂度比最差情况下要小就是了。
稳定性方面，相同的数据在比较过程中不会改变相对的位置，所以冒泡排序是稳定的。
-
梳排序
1、算法分析
梳排序是对冒泡排序的一种改进，因为冒泡排序里比较和交换的步长是1，也就是说每次数据只会跟其相邻的元素比较，这样数据上升的速度比较慢， 而梳排序采取的方法我觉得更形象的来说应该是筛子排序，先用大筛子筛一遍，再用小筛子一层一层的往下筛。比如 说先将比较交换的步长设置为10，也就是说比较交换相差下标10的两个元素，操作完成后，缩小步长，再进行同样的操作，直到步长小于1。其实梳排序最本质的原理我还没有搞清楚，目前看到的书籍也是直接甩出结论：每次将步长除以1.3就可以得到最佳结果，姑且按照这种做法操作吧。
2、程序
void CombSort(int* data,int N)
{
int path = N / 1.3;
while(path >=1)
{
for (int i= 0; i<L-path; i++)
{
if (*(data+i)>*(data +i+ path))
swap(data+i, data + i+path);
}
path = path / 1.3;
}
}
3、算法复杂度与稳定性分析
梳排序的空间复杂度为O(1)，时间复杂度平均情况为O(NlogN)，最坏情况下还是
.
-
希尔排序
-
堆排序
1、算法分析
堆排序实际上是利用完全二叉树来实现排序的一种方法，我们讲的数据结构上的堆本身就是一种完全二叉树，所以这种方法就被称作堆排序。
2、程序
3、复杂度与稳定性分析
-
快速排序
1、算法分析
快速排序的原理就是先选择一个元素作为标杆，将小于该数的元素都放在左边，将大于该数的元素都放在右边。然后将左右两边视作是新的数组，进行同样的操作。这样就有一个问题，该选哪个数作为标杆？当然选哪个数是由你自己决定的，但是如果选的不好就会导致排序的效果很差。例如如果选的数正好是最大的那个数或者最小的那个数，那么会导致其左右两边形成的新数组极度不均衡，算法复杂度并没有降下来。一般来说会选数组中间的那个数作为标杆，这时需要先将中间那个数与数组第一个数交换。
2、程序
void quicksort(int *data, int first, int last)
{
int lower = first + 1;//向右移找比基准点小的数
int upper = last ;//向左移找比基准点大的数
int bound = (first + last) /2;
swap(data[first], data[bound]);
int tmp = data[first];//挖第一个萝卜
while (lower < upper)
{
while (data[upper]>tmp)
upper--;
while (data[lower] < tmp)
lower++;
if (lower < upper)
swap(data[lower], data[upper]);
}
swap(data[upper], data[first]);
if (first <upper)
quicksort(data, first, upper-1);
if (upper < last)
quicksort(data, upper, last);
}
void QuickSort(int *data,int L)
{
quicksort(data, 0, L);
}
3、复杂度与稳定性分析
-
归并排序
归并排序的思路很牛逼，其实就是分治的思想，具体来说就是从最小的元素开始1+1,2+2,4+4.....这样一步一步合起来知道合并成最后的数组。用下面一张图表示可能更加清晰。
2.程序
template<class T>
void merge(T array1[], T temp[], int first, int last) {
int mid = (first + last) / 2;
int i1 = 0, i2 = first, i3 = mid + 1;
while (i2 <= mid && i3 <= last)
if (array1[i2] < array1[i3])
temp[i1++] = array1[i2++];
else temp[i1++] = array1[i3++];
while (i2 <= mid)
temp[i1++] = array1[i2++];
while (i3 <= last)
temp[i1++] = array1[i3++];
for (i1 = 0, i2 = first; i2 <= last; array1[i2++] = temp[i1++]);
}
template<class T>
void mergesort(T data[], T temp[], int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
mergesort(data, temp, first, mid);
mergesort(data, temp, mid + 1, last);
merge(data, temp, first, last);
}
}
template<class T>
void mergesort(T data[], const int n) {
T *temp = new T[n];
mergesort(data, temp, 0, n - 1);
}
3、复杂度与稳定性分析
-
基数排序
1、算法分析
其实我觉得叫基数排序不如叫索引排序那样形象。实际上基数排序的原理就像你在图书馆里根据索引找书差不多，有一级索引、二级索引、三级索引.......在基数排序中一级索引可能就是个位数，二级索引就是十位数，依次类推下去。先根据一级索引对所有数排列遍，一级索引相同放在用一个队列中，一级索引排完之后再根据二级索引排一遍，一直这样擦偶做下去直至将数组按顺序排列。很显然，在排序之前，需要将数组中最大的数据跳出来，以供确定到底有几级索引。
2、程序
void radixsort(int *data, int N)
{
int max = GetMax(data, N);
int INDEX = 1;//位数
queue<int> temp[10];
int fac = pow(10,INDEX);
while (max / fac)
{
INDEX++;
fac = pow(10, INDEX);
}
int factor = 1;
for (; INDEX > 0; INDEX--,factor *= 10)
{
for (int i = 0; i < N; i++)
temp[(data[i] / factor) % 10].push(data[i]);
int k = 0;
for (int j = 0; j < 10;j++)
while(!temp[j].empty())
{
data[k++] = temp[j].front();
temp[j].pop();
}
}
3、复杂度与稳定性分析
-
计数排序
1、算法分析
2、程序
3、复杂度与稳定性分析