【数据结构】--常见的七大经典排序

常见的七大经典排序

引言排序稳定性划分①直接插入排序代码如下 ②希尔排序代码如下 ③选择排序代码如下 ④堆排序代码如下 ⑤冒泡排序代码如下 ⑥快速排序三种改进版本三种快排代码如下 ⑦归并排序代码如下

引言

作为数据结构又一大经典必考面试题，手撕排序算法题是很多人的噩梦，今天我们来梳理探索一下这七大经典算法。明其理，熟其用，穷其变。

排序

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。(来自百度百科)

稳定性划分

所谓稳定性指的是两个想等元素，在排序过程发生之后，两者的先后位置没有发生改变.

①直接插入排序

思想：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

1.元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定

代码如下

void InsertSort(int* a, int n)//直接插入排序 { for (size_t i = 0; i < n - 1; ++i)//让一段无序的数组有序 { int end = i;//从最开始进行比较 int tmp = a[end + 1]; while (end >= 0) { if (tmp < a[end]) { a[end+1]=a[end];//插入到比他大和小的合适位置 //Swap(&a[end + 1], &a[end]); --end; } else { break; } } a[end + 1] = tmp;///插入的位置为-1时 } }

②希尔排序

思想：希尔排序是直接插入排序的优化版本，先选定一个整数，把待排序数组中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

1.时间复杂度：O(N^1.3—N2） 2.稳定性：不稳定

代码如下

void ShellSort(int* a, int n)//希尔排序 { int gap = n-1; while (gap > 1) { gap = gap / 3 + 1; //不断地缩小区间值 for (size_t i = 0; i < n - gap; ++i)// { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end] ; end -= gap; } else { break; } } a[end + gap] = tmp; } } }

③选择排序

思想：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

1.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：不稳定

代码如下

void AdjustDown(int *a, int size, int root) //向下调整算法，升序建大堆，降序建小堆 { int parent = root; int chrild = parent * 2 + 1; while (chrild < size) { if (chrild + 1 < size && a[chrild] < a[chrild + 1]) { ++chrild; } if (a[chrild] > a[parent]) { Swap(&a[parent], &a[chrild]); parent = chrild; chrild = parent * 2 + 1; } else { break; } } } void HeapSort(int *a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0;--i) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]);//将最小的元素交换到最上边 AdjustDown(a, end, 0); --end; } }

④堆排序

思想：堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。此处需要用到向下调整算法，需要注意的是排升序要建大堆，排降序建小堆。

1.堆排序使用堆来选数，效率就高了很多。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(1) 4. 稳定性：不稳定

代码如下

void AdjustDown(int* a, int size,int root)//向下调整算法，升序，建大堆（向下调整算法） { int parent = root; int child = parent * 2 + 1; while (child < size) { if (child + 1 <size && a[child + 1] < a[child]) { ++child; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n)//堆排 { for (int i = (n - 1 - 1) / 2; i >= 0; --i)//建堆 { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0],&a[end]);//将最小的数换到最顶部 AdjustDown(a, end, 0); end--; } }

⑤

⑤冒泡排序

思想：冒泡排序是一种较为简单的排序，因为他的简单粗暴导致它的算法特性差。以升序为例，就是重复遍历数据，比较前后两个元素的大小，把两者大的一个交换到后面，直到把最大的元素调到最后边，最小的调到最前边为止。

时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 稳定性： 稳定排序

代码如下

void BubbleSort(int* a, int n)//冒泡排序（升序） { int end = n - 1; while (end>=0) { int flag = 0; for (int i = 0; i < end; ++i) { if (a[i]>a[i + 1]) { flag = 1; Swap(&a[i], &a[i + 1]); } } if (flag == 0)//若循环走完flag为0，则表示该数列有序 { break; } --end; } }

⑥快速排序

思想：(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

1 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(logN) 4. 稳定性：不稳定

三种改进版本

hoare版本 挖坑法 前后指针版本

三种快排代码如下

int GetMid(int* a, int left, int right)//（三数取中） { assert(a); int mid = left + (right - left) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left]>a[right]) { return left; } else { return right; } } else { if (a[mid] > a[right]) { return mid; } else if (a[left]<a[right]) { return left; } else { return right; } } } int PartSort1(int* a, int left,int right)//三数取中法 { int mid = GetMid(a, left, right); Swap(&a[mid], &a[right]); int key =right; while (left < right) { while (left < right && a[left] <= a[key])//左边找比key大的数 ++left; while (left < right && a[right]>=a[key])//右边找比key小的数 --right; Swap(&a[left], &a[right]); } Swap(&a[key], &a[left]);//当left和right相遇时，交换key和left return left; } void QuickSort1(int* a, int left, int right) { if (right <= left) return; int index = PartSort1(a, left, right);//递归思想 QuickSort1(a, left, index - 1); QuickSort1(a, index + 1, right); } int PartSort2(int* a, int left, int right)//挖坑法 { int key = a[right];//用key记住这个位置 while (left < right) { while (left < right && a[left] <= key)//左边找比key大的 ++left; a[right] = a[left];//找到这个比key大的数据，填到key所在的位置，空出这个位置 while(left < right && a[right] >= key)//右边找比key小的 --right; a[left] = a[right]; //找到这个比key小的数据，填到left所在的位置，空出这个位置 } a[left] = key;//当left和right相遇时，把key填到left位置 return left; } void QuickSort2(int* a, int left, int right) { if (right <= left) return; int index = PartSort2(a, left, right);//递归思想 QuickSort2(a, left, index - 1); QuickSort2(a, index + 1, right); } int PartSort3(int* a, int left, int right) //左右指针法 { int cur = left; int prev = left - 1; int key = a[right]; while (cur< right) { if (a[cur] < key && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } ++prev; Swap(&a[prev],&a[right]); return prev; } void QuickSort3(int* a, int left, int right) { if (right <= left) return; int index = PartSort3(a, left, right);//递归思想 QuickSort3(a, left, index - 1); QuickSort3(a, index + 1, right); }

⑦归并排序

思想：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(N) 4. 稳定性：稳定

代码如下

void _MergeSort(int* a, int left, int right, int* tmp)//归并排序 { if (left == right) return; int mid = left + (right - left) / 2; // [left, mid] [mid+1, right]分别有序 _MergeSort(a, left, mid, tmp); _MergeSort(a, mid + 1, right, tmp); // a[left, mid] a[mid+1, right]归并到tmp[left, right] int begin1 = left, end1 = mid; int begin2 = mid + 1, end2 = right; int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1]; ++begin1; } else { tmp[i++] = a[begin2]; ++begin2; } } while (begin1 <= end1) { tmp[i++] = a[begin1]; ++begin1; } while (begin2 <= end2) { tmp[i++] = a[begin2]; ++begin2; } memcpy(a + left, tmp + left, sizeof(int)*(i - left)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)* n); _MergeSort(a, 0, n - 1, tmp); free(tmp); }