摘要：当到达时等同于直接插入排序，此时序列已基本有序，所有记录在统一组内排好成有序序列。当面对大量数据时，希尔排序将比直接插入排序更具优势图示讲解第一趟取增量，所有间隔为的元素分在一组，在各个组中分别进行直接插入排序。
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
排序实现的接口：
//打印序列void PrintArray(int* a, int n);//直接插入排序void InsertSort(int* a, int n);//希尔排序void ShellSort(int* a, int n);//选择排序void SelectSort(int* a, int n);//堆排序void HeapSort(int* a, int n);//冒泡排序void BubbleSort(int* a, int n);//快排void QuickSort(int* a, int left,int right);void QuickSortNonR(int* a, int left, int right);//归并排序void MergeSort(int* a, int n);void MergeSortNonR(int* a, int n);//计数排序void CountSort(int* a, int n);是一种最简单的排序，将元素逐个插入到已排好序的有序表中，从而得到一个新的，容量增1的有序表。
将r[i]与r[i-1],r[i-2],…,r[0],从后向前顺序比较，在往前比较的过程中同时
后移比自身大的元素。
void InsertSort(int* a, int n){ int i; for (i = 0; i < n - 1; i++) { int end = i; int tmp = a[end + 1]; while (end>=0) { if (a[end] > tmp) { a[end + 1] = a[end];//比待插入元素更大的元素需要后移 end--;//从后往前寻找插入点 } else { break;//找到end后退出循环 } } a[end + 1] = tmp;//在end之后插入 }}
时间复杂度
代码中的循环次数取决于待插元素与前i-1个元素的大小关系
最好情况，序列原本已为顺序，只需遍历一遍数组，无需移动——O(N)
最坏情况，序列为逆序，每次待插元素需要逐步走向队头，那么总的比较次数（移动次数）为一个等差数列的和，最后一个元素需要比较n-1次才能走到队头——O(n^2).空间复杂度
只需要一个记录待插元素的辅助空间tmp，所以空间复杂度为O(1).
稳定性：插入排序是稳定的排序算法，满足条件r[j] > r[j + 1]才发生交换，这个条件可以保证值相等的元素的相对位置不变
希尔排序是插入排序的一种，又称缩小增量法。
希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成n/gap个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。
然后，gap折半，重复上述分组和排序的工作。当到达gap==1时（等同于直接插入排序），此时序列已基本有序，所有记录在统一组内排好成有序序列。
当面对大量数据时，希尔排序将比直接插入排序更具优势
- 第一趟取增量gap=5，所有间隔为5的元素分在一组，在各个组中分别进行直接插入排序。
我们可以根据这个特性，先写出一部分代码：
for (int i = 0; i < n - gap; i++) { //单个数字 int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }
- 第二趟增量取之前增量的一半，即gap=2，所有间隔为2的元素分在一组，在各个组中直接插入排序。
- 第三趟gap=1，对整个序列进行一趟直接插入排序，由于已基本有序，这次的直接插入排序将会省去不少时间。
void ShellSort(int* a, int n){ int gap = n; while (gap > 1) { gap = gap / 2; //单个gap组 for (int i = 0; i < n - gap; i++) { //单个数字 int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }}
- 时间复杂度
当gap>1时，元素不是一步步移动，而是跳跃式移动，当进行最后的直接插入排序时，序列以基本有序，只要做少量的比较和移动即可完成排序。希尔排序的时间复杂度取决于gap的选择，这涉及一些数学上尚未解决的难题。在前人大量的实验基础上推出，当序列长度n在特定范围内，时间复杂度为O(n^1.3),当n->∞时，可减少到O(n*log(n)).- 空间复杂度
只需要一个辅助空间——O(1)
不稳定，相同的值预排时被分到不同的组里
在数组r[0…(n-1)]中，第一趟从r[0]开始，通过n-1次比较在n个元素中找到最小的元素并与r[0]互换。
第二趟从r[1]开始，通过n-2次比较，在n-1个元素中找到最小的元素并于r[1]互换。
依次类推，经过n-1趟，排序完成。
void Swap(int* a, int* b){ int tmp = *a; *a = *b; *b = tmp;}void SelectSort(int* a, int n){ int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = end; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i; } if (a[i] > a[maxi]) { maxi = i; } } //互换函数 Swap(&a[begin], &a[mini]); //begin==maxi时，最大的被换到了mini的位置了，需要对maxi调整 if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); begin++; end--; }}
- 时间复杂度
无论初始的序列排列如何，元素之间依然需要通过遍历去比较大小，确定单个最值的时间复杂度为等差数列之和(n^2/2),同时确定最大和最小值的时间复杂度(n ^2/4)。不管原序列是无序，有序或接近有序，选择排序的时间复杂度皆为O(n ^2),
空间复杂度
一个辅助空间或两个辅助空间——O(1)
堆的定义：简而言之，将数组按层序排成的完全二叉树，称之为堆
如果二叉树的双亲结点大于孩子结点——大根堆
如果二叉树的双亲结点小于孩子结点——小根堆
之后我们需要进一步调整，将堆调整成为大根堆(小根堆)。大小根堆可保证堆顶为当前数组的
最值
那么我们如何对堆进行调整呢？
- 首先我们需要了解一下堆的性质
如果当前索引值下标为i，
双亲结点的下标parent=(i-1)/2
左孩子结点的小标child1 =2*i+1
右孩子结点的下标child2 =2*i+2
了解这一基本性质后，我们就可以对堆进行调整了。
以建大根堆作为演示
向下调整
从最后一个非叶子结点parent开始，让其与孩子结点进行比较，如果孩子结点比k大，那么k便往下与孩子结点互换，直到孩子的下标越界，说明该结点调整结束。
然后继续对上一个非叶子结点的子树进行向下调整，直到达到整个堆的根结点，堆调整结束。最后一个非叶子结点的下标parent的计算
数组长度为n，那么最后一个叶子结点下标为n-1，其双亲结点就是最后一个非叶子结点，于是parent=(n-1-1)/2
- 单颗子树根结点向下调整的代码实现//向下调整void AdjustDown(int *a,int n,int parent)//a-数组，n-数组大小，parent-向下调整的起始位置{ int child = parent * 2 + 1;//完全二叉树必先有左孩子 while (child < n)//当孩子越界时，说明双亲已达叶子结点，结束当前调整 { if (child + 1 < n && a[child+1]>a[child])//找到两个孩子中的较大者 { child++; } if (a[child] > a[parent])//如果孩子比双亲大则互换 { Swap(&a[child], &a[parent]); parent = child;//双亲向下继续调整 child = parent * 2 + 1;//孩子随着双亲一起改变 } else { break;//双亲已比孩子大亦无必要调整，因为下面的子树先前已成大根堆 } }}如果我们需要排为
升序，则应建立大根堆。
同样我们需要排为降序，则应建立小根堆。
由堆的性质，我们只能唯一确定堆顶的是最值，
(1). 将得到的堆顶最值与堆尾元素互换，堆容量-1
(2).堆顶向下调整，选出剩余元素的最大值放置堆顶，
(3). 继续执行(1)(2)，直到堆容量为1，堆排序完成。
void HeapSort(int* a, int n){ //建堆 升序建大堆 int i = 0; //向下调整建堆 for (i = (n-1-1)/2; i >=0; i--)//i从最后一个非叶子结点走向根结点 { AdjustDown(a, n, i); } //把堆顶与堆尾互换不再理会，堆顶再向下调整 for (i = 0; i < n; i++) { Swap(&a[0], &a[n - i - 1]); AdjustDown(a, n - i - 1, 0); }}绿圈为
已满足大根堆性质的树
紫圈为进行向下调整
黄圈为堆顶和堆尾交换过程
红圈为已排完序的元素
堆排序的时间主要耗费在建初堆和调整堆时进行的反复筛选上。
建初堆的移动步数：
第h-1层，2^(h-2)个结点向下移动1层
…
第3层，2^(2)个结点，向下移动h-3层
第2层，2^(1)个结点，向下移动h-2层
第1层，2^(0)个结点，向下移动h-1层
T(n)=2^(0)* (h-1)+2 ^(1)* (h-2)+…+2^(h-2)1
利用错位相减法，得到T(n)=n-log2(n+1)≈n
建堆的时间复杂度为O(n)
调整堆需要将堆顶的元素不断的移向堆尾，则复杂度为元素个数二叉树高度——O(n*logn)
空间复杂度，只借助了一个辅助空间——O(1)
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
- 比较相邻的两个数，如果第一个数比第二个数大，则两数交换。对之后的相邻元素进行同样的工作，从开始到最后一对，这样进行一次排序后，数据的最后一位会是最大值，第一次循环进行的次数为 r.length-1。之后对所有的元素重复以上的步骤，且以后每次循环的次数为r.length-1-i（i为循环第几次 ，i 从零开始）；重复上述步骤，直到排序完成
void BubbleSort(int* a, int n){ //优化 //已经有序 提前结束 for (int j = 0; j < n; j++) { int exchange = 0; for (int i = 1; i < n - j; i++) { if (a[i] < a[i - 1]) { Swap(&a[i], &a[i - 1]); exchange = 1; } } if (exchange == 0)//没有发生过互换的情况，说明已经有序 { break; } } }时间复杂度
最好的时间复杂度O(n)–有序只需要遍历一遍
最差的时间复杂度O(n^2)——逆序，等差数列之和
空间复杂度，只借助了一个辅助空间——O(1)
快速排序是由冒泡排序改进而得的。
在冒泡排序的过程中，每次遍历只对相邻元素进行比较，每次交换只能消除一个逆序。
如果能通过两个(不相邻的)元素的交换消除多个逆序，则会大大加快排序的速度，快速排序的一次交换可以消除多个逆序。
单趟排序*（递归 or 迭代）：//逻辑void Partition(){ ...}void QuickSort(int *a,int n){ 迭代 or 递归 { Partition()//单趟排序函数 }}重要）a.在序列的n个元素中，选择一个元素（一般选择第一个元素）作为
枢轴，将其设为关键字keyi，在经历一次单趟排序后，所有小于keyi的元素交换到前面，把所有大于keyi的元素都交换到后面，单趟排序完成。
b.然后，将待排序的元素以keyi为界，分为左右两个子表，再分别对左右子表
重复上述步骤。
c.直至每个子表
不含元素或只有一个元素时（控制结束条件），排序完成。
我们有三种方法可以完成单趟排序这一步骤，分别为
Hoare算法，pivot法(挖坑法)和前后指针法。
a.选定下标作为基准值
keyi，一般将keyi定在左端或者右端
b.我们再选定两个指针left，right分别位于序列的左侧和右侧。
c.如果keyi定在左侧则right先向左边遍历，如果keyi定在了右侧则left先向右边遍历。
d.这里我们假设keyi定在左侧，right先开始向左遍历，直至遇到比a[keyi]小的值则停下。然后left开始向右遍历，遇到比a[keyi]大的值则停下。然后互换左右下标对应值，Swap(&a[left],&a[right])。
e.然后继续right先走，left后走，直至left==right时，Swap(&a[keyi],&a[left]),这样便完成了单趟排序。
这里的
p也就是前文中提到的keyi，不过这里设置在了右端（a[keyi]为6），可以发现left先开始了遍历，找到了比keyi大的值，a[left]
为8，right随后找到了比keyi小的值，a[right]为4，两者调换完后继续遍历，直到left撞上right，将left和right共同指向的值9，与a[keyi]互换，完成单趟遍历。
int Partition1(int* a, int left, int right){ int keyi = left;//将keyi定在左侧，则右端先走，反之则左端先走 while (left < right) { //右端先走,对于升序，找到比a[key]小的值则停下 while (right > left && a[right] >= a[keyi])//保证是大于等于号 { right--; } //left找比a[key]大的值停下 while (left < right && a[left] <=a[keyi])//保证是小于等于号 { left++; } Swap(&a[left], &a[right]);//交换左右，比keyi小的放左边，大的放右边 } Swap(&a[keyi], &a[left]); return left;}
- 具体思路：
a.以左端作为基准值，将下标记为关键字pivot（枢轴），令keyi=a[pivot]。
b.分别用关键字left和right记录左右端下标。
c.right往左遍历，遇到比keyi小的数字时，将a[right]填入a[pivot]中，
再让pivot=right(将坑位留在right处)。
d.此时让left往右遍历，遇到比keyi大的数字，将a[left]填入a[left]中，
再让pivot=left（将坑位留在left处）。
e.之后依旧是right先动，left后动，直至left与right重合（此时left==right，right= =pivot）,使a[pivot]=keyi,单趟排序结束。
动图演示
代码实现
//单趟排序的第二种方法——挖坑法int Partition2(int* a ,int left, int right){ int keyi=a[left]; int pivot = left; while (left < right) { //key在左端，则从右端开始找 //右边找小，放到左边的坑中，自己再成坑 while (left < right && a[right] >= keyi) { right--; } a[pivot] = a[right]; pivot = right; //左边找大，放到右边的坑中，自己再成坑 while (left < right && a[left] <= keyi) { left++; } a[pivot] = a[left]; pivot = left; } a[pivot] = keyi; return pivot;}
- 基本原理
a.初始化：选择一端下标设为基准值keyi，需要两个指针，一个在前一个在后，分别用cur表示前指针，prev表示后指针(这里的指针的意思是待排序数列的下标)，我们规定cur在prev的后一个位置。prev指向这个数列开始的第一个，cur指向prev的后一个位置。
b.如果cur的值大于基准值a[key]，这时只让cur++,如果a[cur]小于基准值，这时我们让prev++后，判断是否与cur的位置相等，若相等，cur继续向后遍历，若不相等，则交换cur和prev的值。c.直到
cur超过序列末尾时，我们再交换prev和基准值，这样基准值的位置也就确定了。
keyi选在左端，那么cur从left+1开始 走到right，prev从cur-1开始。
cur走到终点时，[left+1,prev]都是比a[keyi]小的数字，[prev+1,right]都比a[keyi]大。
所以a[prev]和a[keyi]互换，使a[keyi]正确落位。
//以左端为keyiint Partition3(int* a, int left, int right){ int keyi = left; int cur = left + 1, prev = left; while (cur <= right) { if (a[cur] < a[keyi] && (++prev)!=cur) { Swap(&a[cur], &a[prev]); } cur++; } Swap(&a[prev], &a[keyi]); return prev;}如果以右端为keyi则有小小的改动
keyi选在右端，那么cur从left开始 走到right-1，prev从cur-1开始。
cur走到终点，[left,prev]都是比a[keyi]小的数字，[prev+1,right-1]都比a[keyi]大。
所以a[keyi]和a[prev+1]互换，以使a[keyi]正确落位。
int Partition4(int* a, int left, int right){ int keyi = right
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125387.html
摘要：本篇博客我要来和大家一起聊一聊数据结构初阶中的最后一篇博客八大经典排序算法的总结，其中会介绍他们的原来，还有复杂度的分析以及各种优化。快速排序递归版本快速排序是于年提出的一种二叉树结构的交换排序方法。 ...
阅读 3745·2023-01-11 11:02
阅读 4250·2023-01-11 11:02
阅读 3062·2023-01-11 11:02
阅读 5187·2023-01-11 11:02
阅读 4749·2023-01-11 11:02
阅读 5546·2023-01-11 11:02
阅读 5325·2023-01-11 11:02
阅读 4011·2023-01-11 11:02
