排序

  • 一.插入排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
    • 4.稳定性分析
  • 二.希尔排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
    • 4.稳定性分析
  • 三.快速排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
    • 4.稳定性分析
    • 5.代码改进
  • 四.归并排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
    • 4.稳定性分析
  • 五.堆排序
    • 1.复杂度分析
    • 2.稳定性分析
  • 六.计数排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
    • 4.稳定性分析
  • 七.冒泡排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
  • 八.选择排序
    • 1.代码思路
    • 2.代码实现
    • 3.复杂度分析
  • 九.总结

一.插入排序

1.代码思路

我们在生活中打扑克时,是一张牌一张牌地摸的,当我们每摸一张牌就插入到前面已经排好序的牌中,摸牌之后整副牌就是有序的了。插入排序也是这个思路:假设现在任意给我们一个拥有6个元素的整型数组,我们可以先把0号元素看成是有序的,把1号元素往前面插入,那么0号到1号元素就是有序的了,接着把2号元素也往前插入,以此类推,等5号元素也往前插入后整个数组便是有序的了。

2.代码实现

void InsertSort(int* a, int n){int cur = 1;while (cur < n){int pos = cur-1;int key = a[cur];//记录当前要进行插入的数while (pos >= 0){if (a[pos] > key){a[pos + 1] = a[pos];//数据后移}else{break;}--pos;}a[pos + 1] = key;//将本轮要前插的数据移动到相应位置++cur;}}

有的人对直接插入排序进行了优化,在把数据往前插入时,既然前面的数据已经有序了,我们就可以使用二分查找寻找要插入的位置,这提高了查找的效率,但数据移动的次数还是没有变,这就是所谓的折半插入排序,这里不过多赘述。

3.复杂度分析

空间复杂度:O(1)
时间复杂度O(n^2)
最坏情况下,第1个数据插入要移动0次,第2个要移动1次…第n个要移动n-1次,累加起来,最坏情况下时间复杂度就是O(n^2)

4.稳定性分析

由于我们在控制移动时,只有要前插的数据小于他前面的数据时(假设我们现在要排升序),我们才移动数据,大于和等于均不移动,故排序是稳定的。我们也可以看出当数据集合越接近有序,排序的效率就越高(并不是所有的排序越接近有序效率就越高)。

二.希尔排序

1.代码思路

既然我们知道进行直接插入排序排序时,数据集合越有序排序的效率就越高,那我们先对数据进行与排序,最后再进行一次直接插入排序。
假设现在我们有一个10个数据的数据,我们可以先把间隔为5的作为一组数据进行插入排序,即把(0,5)、(1,6)、(2,7)、(3,8)、(4,9)这五组数据分布进行一次插入排序,接着把间隔为3的数据作为一组数据,即(0,3,6,9)、(1,4,7)、(2,5,8)这3组数据进行一次插入排序,最后再把间隔为1的数据进行一次插入排序(即对整个数据进行一次插入排序),那么整个数据集合便是有序的了。注意:最后一次插入排序时数据间隔必须为1.
现在我们要考虑的就是这个间隔应该怎么取值比较合适呢?
现在较多人使用的方法是先让gap=n(数组长度),接着让每趟排序的gap=gap/3+1。

2.代码实现

void ShellSort(int* a, int n){int gap = n;int i = 0;int j = 0;while (gap > 1)//进行多趟,直至gap为1{gap = gap / 3 + 1;for (i = 0; i < gap; ++i){//进行直接插入排序for (j = i; j < n; j += gap){int key = a[j];int pos = j - gap;while (pos >= i){if (a[pos] > key){a[pos + gap] = a[pos];}else{break;}pos -= gap;}a[pos + gap] = key;}}}}

3.复杂度分析

空间复杂度:O(1)
时间复杂度O(n^1.25)到
O(1.6n^1.25)
希尔排序的时间复杂度不好计算,不过其于O(NlogN)是一个量级的(实际上会比这个大一点)。

4.稳定性分析

属于不稳定排序

三.快速排序

1.代码思路

假设现在给我们一个整型数组,我们可以先在数组里面任意拿一个值value(一般都是找第一个),我们现在想达到这样一个效果:在数组里面找到一个位置把value放进去,同时value左边的值都比value小(我们现在要排升序),右边的值都比value大,那么value就一定放到了整个排序的正确位置上,接着又可以对value左边的数据和右边的数据分别进行以上操作,依此类推,直到要进行操作的数据个数小于等于1。

接下来就是要如何达到我们想要的效果了,我们可以用左右指针的方法(hoare版本),左指针指向数组最左边,右指针指向数组最右边,右指针指向的值如果大于等于value,就往左走,小于value就停下来,左指针指向的值如果小于等于value,就往右走,大于value就停下来,接着交换左右指针指向的值,直至左右指针相遇。注意:如果我们要排升序,一定要先让右指针先走,这样左右指针相遇的位置的值小于等于value(后面会说明)。交换value和左右指针相遇的位置的值,至此,我们想要的效果就达成了。
下面的动图借用了Kimi-zhang的文章里的动图作为演示:

说明:
相遇只有两种情况:左指针遇上右指针、右指针遇上左指针
①左指针遇上右指针:
因为是右指针先走,所以左指针往右走相遇位置遇到的值一定比value小
②右指针遇上左指针:
由于左指针上的值一定小于等于value,所以右指针往左走相遇位置遇到的值一定小于等于value

2.代码实现

int PartSort1(int* a, int left, int right){Swap(&a[left], &a[mid]);int key = a[left];int keypos = left;while (left < right){while (left < right && a[right] >= key)//1{--right;}while (left < right && a[left] <= key)//2{++left;}Swap(&a[left], &a[right]);}Swap(&a[keypos], &a[left]);//先1后2,相遇点的值一定比key小return left;}void QuickSort(int* a, int left, int right){if (left >= right){return;}int mid = PartSort1(a, left, right);QuickSort(a, left, mid - 1);QuickSort(a, mid+1, right);}

3.复杂度分析

空间复杂度:O(logN)
由于递归要调用栈帧,其深度一般为logN(当然了,如果数据特殊,如已经有序,那么栈的深度就为N)。
时间复杂度:N(logN)
函数一般要调用logN层,每层最坏情况下交换N次,故时间复杂度为O(NlogN)。当然了,如果数据是有序的,其时间复杂度就会达到O(N^2),故快排适用于数据集合无序。

4.稳定性分析

不稳定排序

5.代码改进

由于我们每次都是取数组第一个元素将其分成左右两部分,故当数组有序时,总有一部分的元素个数为0,另一部分的元素个数为N-1,其空间和时间复杂度会大大增加,我们希望可以取到一个数,将数组平分为左右两部分,这样就算有序,其时间复杂度就会降到O(NlogN),空间复杂度也会降到O(logN)。那我们可以在数组的左边,右边和中间位置各取一个值,将这3个值的中大小处于中间的数作为value,这样就把有序的情况优化掉了,对无序情况基本没什么影响。

//三数取中int GetMid(int* a, int left, int right){int mid = left + (right - left) / 2;if (a[left] < a[right]){if (a[mid] < a[left]){return left;}else if (a[mid] > a[right]){return right;}else{return mid;}}else if (a[left] > a[right]){if (a[mid] < a[right]){return right;}else if (a[mid] > a[left]){return left;}else{return mid;}}return left;}//交换两个数void Swap(int* num1, int* num2){int temp = *num1;*num1 = *num2;*num2 = temp;}// 1.快速排序hoare版本int PartSort1(int* a, int left, int right){//利用三数取中极大优化原数集接近有序的情况int mid = GetMid(a, left, right);Swap(&a[left], &a[mid]);int key = a[left];int keypos = left;while (left < right){while (left < right && a[right] >= key)//1{--right;}while (left < right && a[left] <= key)//2{++left;}Swap(&a[left], &a[right]);}Swap(&a[keypos], &a[left]);//先1后2,相遇点的值一定比key小return left;}void QuickSort(int* a, int left, int right){if (left >= right){return;}int mid = PartSort1(a, left, right);QuickSort(a, left, mid - 1);QuickSort(a, mid+1, right);}

前面所说的将划分的数组进行排序的部分都是hoare版本的,下面看看另外的版本
①挖坑法版本

int PartSort2(int* a, int left, int right){//利用三数取中极大优化原数集接近有序的情况int mid = GetMid(a, left, right);Swap(&a[left], &a[mid]);int key = a[left];while (left < right){while (left < right && a[right] >= key){--right;}a[left] = a[right];while (left < right && a[left] <= key){++left;}a[right] = a[left];}a[left] = key;return left;}

②前后指针版本

int PartSort3(int* a, int left, int right){//利用三数取中极大优化原数集接近有序的情况int mid = GetMid(a, left, right);Swap(&a[left], &a[mid]);int key = a[left];int pre = left;int cur = pre + 1;while (cur <= right){if (a[cur] < key && ++pre != cur){Swap(&a[pre], &a[cur]);}++cur;}Swap(&a[left], &a[pre]);return pre;}

这些版本的复杂度并无区别,只不过用不同的方式把数组分为左右两部分。

四.归并排序

1.代码思路

现在我们有一个长度为15的整型数组,我们把数组从中间分开分成2部分,我们希望他左半部分和右半部分都是有序的,那我们只需要将这两半部分合并,那整个数组就是有序的了。既然这样,那我们又可以将左半部分和右半部分分别各再分割成2部分,如此一直进行下去,直至某一部分只剩一个元素,我们可以认为单个元素是有序的,之后就是两两归并,那整个数组便是有序的了。

现在问题在于归并时怎么归并,如果在原数组归并,其时间复杂度就会比较大(至少比O(N)大),但如果我们使用一个临时数组,采用合并有序表的思路,将数据不断加入到临时数组里面,最后再把数据拷贝会原数组,那时间复杂度就会降到O(N)。

2.代码实现

void PartMergeSort(int* a, int* temp, int begin,int end){if (end <= begin){return;}//分治int mid = begin + (end - begin) / 2;PartMergeSort(a, temp, begin, mid);PartMergeSort(a, temp, mid+1, end);//归并int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int pos = 0;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[pos++] = a[begin1++];}else{temp[pos++] = a[begin2++];}}while (begin1 <= end1){temp[pos++] = a[begin1++];}while (begin2 <= end2){temp[pos++] = a[begin2++];}memcpy(a + begin, temp, pos*sizeof(int));}void MergeSort(int* a, int n){int* temp = (int*)malloc(n * sizeof(int));if (NULL == temp){perror("malloc");exit(0);}PartMergeSort(a, temp, 0, n - 1);}

3.复杂度分析

空间复杂度:O(N)
由于开辟了一个大小为N数组
时间复杂度:O(NlogN)

无论原数组是有序还是无序,其复杂度都不变,故当原数据集接近有序时,可以先考虑别的排序。

4.稳定性分析

由于在归并时,如果两数相等,我们可以控制其先让左边的数据入临时数据,故归并排序是稳定的。

五.堆排序

关于堆排序本人已经写过一篇详细的博客堆排序

1.复杂度分析


故堆排序
时间复杂度为为O(NlogN)
空间复杂度为O(1)

2.稳定性分析

不稳定排序

六.计数排序

1.代码思路

假如我们现在有一个数组a[3,2,2,2,1,1,1,3,3,5,6,7,5,6],我们想要对其排序,我们可以定义一个大小为6数组b,遍历数组a,将a中的值作为b数组的下标并在该位置上加1,遍历完数组a后,再遍历数组b,如果该位置的值非零则将该位置的下标作为值放入a中,直至b数组在该位置的值为0。
由于a数组的最小值可能会比较大,我们可以找到数组a的最大值max和最小值min,开辟大小为max-min大小的数组b。

由此我们可以知道计数排序只适用于数据比较集中的非负整数排序

2.代码实现

// 计数排序void CountSort(int* a, int n){int maxNum = a[0];int minNum = a[0];int i = n;//寻找最大值和最小值while (i--){if (a[i] > maxNum){maxNum = a[i];}else if (a[i] < minNum){minNum = a[i];}}int size = maxNum - minNum + 1;int* temp = (int*)malloc(size * sizeof(int));if (NULL == temp){perror("mallloc");exit(-1);}memset(temp,0, size * sizeof(int));//计数i = n;while (i--){temp[a[i] - minNum]++;}//排序int pos = 0;for (i = 0; i < size; i++){while (temp[i]--){a[pos++] = i + minNum;}}free(temp);}

3.复杂度分析

假设数组最大值和最小值之差为K
空间复杂度:O(K)
时间复杂度:O(N+K)
遍历a数组花去N,遍历b数组花去K

4.稳定性分析

计数排序属于稳定排序,具体可见计数排序

七.冒泡排序

1.代码思路

假如现在我们要对一个数组排升序,我们可以让一个指针指向数组首元素,前后比较,将大的往后面交换,接着指针后移,遍历完数组后,最大值就到数组末尾去了,接着再将指针指向数组首元素,重复上述操作N-1次就完成排序了。

2.代码实现

void BubbleSort(int* a, int n){int i = 0;int j = 0;for (i = 0; i < n; ++i){int flag = 0;for (j = 0; j+1 < n - i; ++j){if (a[j] > a[j + 1]){int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;flag = 1;}}if (!flag){break;}}}

3.复杂度分析

空间复杂度:O(1)
时间复杂度:O(N^2)
属于稳定排序

这个排序几乎没什么用,唯一的用途就是用于学排序的新手教学。

八.选择排序

1.代码思路

先遍历一遍数组,找到最小值,然后与数组第一个元素交换,接着再从剩下的元素里找最小值,与数组第二个元素交换,直至剩下的元素个数为1,一个升序数组就完成了。

2.代码实现

void SelectSort(int* a, int n){int i = 0;int j = 0;for (i = 0; i < n; ++i){int minPos = i;for (j = i; j < n; ++j){if (a[j] < a[minPos]){a[minPos] = a[j];}}int temp = a[i];a[i] = a[minPos];a[minPos] = temp;}}

3.复杂度分析

空间复杂度:O(1)
时间复杂度:O(N^2)
属于稳定排序

这个排序几乎没什么用,新手教学也很少用

九.总结

下面给出常见排序的复杂度和稳定性表格:

如果本文有什么不对的,恳请指正。编写不易,如若本文对读者有所帮助,点个赞给博主充充电吧!