第五章 数据结构与算法——排序

目录

一、排序的概念及其运用

二、八大排序的原理及其实现（升序为例）

（一）、直接插入排序

（二）、希尔排序（也叫缩小增量排序）（重要）

1.原理：

2.该排序一般分为两个步骤：

3.预排序过程：

4.预排序的意义（升序为例）：

5.希尔排序的特点：

6.希尔排序代码实现：

（三）、堆排序

（四）、直接选择排序

（五）、快速排序（2023_09_21）

---

一、排序的概念及其运用

（一）、排序的概念

1、所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

2、 稳定性 ：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j] 之前，则称这种排 序算法是稳定的；否则称为不稳定的。

举例：

例如一组数组中有三个相同的数字 3(a)、3(b)、3(c),，且 3(a) 的位置在 3(b) 前面，3(b)的位置在3(c)的前面，则排序过后，这三个3的相对位置没有改变，则称该排序算法是 稳定 的。

3、内部排序 ：数据元素全部放在内存中的排序。

4、外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二、八大排序的原理及其实现（升序为例）

（一）、直接插入排序

1.原理：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

2.特点：

①：元素的集合越接近有序，该算法的时间效率就越高；

②：时间复杂度：O(N^2)；

③：空间复杂度：O(1)；

3.代码实现：

//直接插入排序
//升序为例
void Insert(int* arr, int n)
{for (int i = 0; i<n-1; i++){int end = i;//保存即将参与排序的第一个数（即end+1位置的数）,防止移动数据时，该数被覆盖int tmp = arr[end + 1];while (end >= 0){//挪动数据if (arr[end] > tmp){arr[end + 1] = arr[end];}else{break;}end--;}//插入数据arr[end + 1] = tmp;}
}int main()
{int arr[7] = { 3,6,10,4,8,2,1 };//参数一是数组，参数二是数组元素个数Insert(arr, 7);return 0;
}

（二）、希尔排序（也叫缩小增量排序）（重要）

1.原理：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序（预排序）。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

2.该排序一般分为两个步骤：

①： 预排序

②：直接插入排序

3.预排序过程：

分组进行排序，间距为gap一组，如下：

后面我们会讨论gap的取值，但这里我们会发现：

当gap = 1时，就是直接插入排序，

并且通常 预排序会进行多次，以便更加接近有序。

4.预排序的意义（升序为例）：

①：大的数更快的跑到右边去，小的数更快跑到前面去；

②：gap越大，跳的越快（分组越少），越不接近有序；

③：gap越小，跳的越慢（分组越多），越接近的有序；

④：当gap = 1时，该排序为直接插入排序；

5.希尔排序的特点：

①： 希尔排序是对直接插入排序的优化。

②：希尔排序的 时间复杂度不好计算 ，因为gap在动态变化，有人进行大量计算，最后我们取 O(n^1.3) ，但可以通过一些测试证明出他是直接插入排序的优化，比直接插入排序的效率要高；（2023_09_19）

③：稳定性：不稳定；

6.希尔排序代码实现：

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//外层while循环就是进行多次预排序的操作//下面时库里面的两种规定，第一种是gap每次减少一半//因为任何整形连续除以2，最终都会等于1//所以当gap不等于1时，相当于在进行预排序，一步一步接近有序//当gap等于1时，进行直接插入排序//设置下面gap的两种方式是防止预排序次数不合适，若规定预排序的次数，则有时数组的数量或多或少//就会造成不合适，所以我们要设置来与数组的个数n有关联gap /= 2;//gap/=3+1；for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}int main()
{int arr[] = { 9,1,2,5,7,4,8,6,3 };ShellSort(arr, sizeof(arr) / sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

（三）、堆排序

堆排序二叉树部分小编已经讲过了，所以在这里小编不过多叙述，感兴趣的小伙伴可以参考文章：堆排序http://t.csdnimg.cn/crfOK

1.原理：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.堆排序的特点：

①：堆排序使用堆来选数，效率就高了很多；

②：时间复杂度： O(N*logN)；

③： 空间复杂度： O(1)；

④： 稳定性：不稳定。

3.堆排序的代码实现（具体过程参考文章： http://t.csdnimg.cn/crfOK ）

//堆排序
void HeapSort(int* a, int n)
{//建堆(以降序建小堆为例)for (int i = 0; i < n; i++){AdjustUp(a, i);}//记录堆尾的下标int end = n - 1;//开始排序while (end > 0){//交换堆顶和堆尾Swap(&a[0],&a[end]);//向下调整AdjustDown(a, end, 0);end--;}

（四）、直接选择排序

1.原理：每一次从待排序的数据元素中选出最小的和最大的元素，分别存放在序列的起始位置，和末位置，直到全部待排序的数据元素排完 。

2.直接选择排序的特点：

①：直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用；

②：时间复杂度：O(N^2)；

③：空间复杂度：O(1)；

④：稳定性：不稳定；

3.直接选择排序的代码实现：

//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min = begin;int max = begin;for (int j = begin+1; j <=end; j++){if (arr[j] > arr[max]){max = j;}if (arr[j] < arr[min]){min = j;}}Swap(&arr[begin], &arr[min]);//如果最大值下标max与begin相等，则上述交换函数会把最大值交换到下标为min的位置，所以要记录一下if (max == begin){max = min;}Swap(&arr[end], &arr[max]);begin++;end--;}
}int main()
{//int arr[7] = { 3,6,10,4,8,2,1 };//直接选择排序SelectSort(arr, sizeof(arr) / sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

①：首先创建两个变量begin和end来记录待排序数组的首尾位置下标，然后每选出一组最大最小数排序后，begin++，end--就更新了待排序数组的首尾位置下标，直到begin>end时代表排序结束；

②：然后创建两个变量min，和max分别记录最小值的下标和最大值的下标，因为这是一个寻找的过程，所以刚开始都初始化为begin，然后依次将待排序数组里面的数与该下标的值进行比较，若找到更小或更大的值，则更新下标，每找一次（for循环结束）就将下标为min的数与待排序数组的首位置下标begin的数进行交换，下标为max的数与待排序数组的末位置下标max的数进行交换，但要注意如果max等于begin的话，当你进行最小值min和begin交换的时候，begin位置为最大值会被交换到min的位置，所以这时要更新一下最大值的下标max，即将max更新成min.

​

（五）、快速排序（2023_09_21）

1.原理：任取待排序元素序列中的某元素作为基准值（习惯称为key），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.原理图：

3.快速排序特点：

①：快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫 快速 排序；

②：时间复杂度： O(N*logN)；

③：空间复杂度： O(logN)；

④：稳定性：不稳定；

4.快速排序的代码实现（有几种方法）

//三数取中（left,mid,right中找第二大那个作为key）
int GetMid(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[left] < arr[mid]){if(arr[mid]<arr[right])//right最大{return mid;}else if(arr[left]<arr[right])//mid最大{return right;}else{return left;}}else{if (arr[right] < arr[mid])//left最大{return mid;}else if(arr[left]<arr[right])//mid最小{return left;}else{return right;}}}//快排的单趟排序
int PartSort(int* arr, int left, int right)
{int midi = GetMid(arr, left, right);Swap(&arr[left], &arr[midi]);int keyi = left;while (left < right){while (arr[right] >= arr[keyi] && left < right){right--;}while (arr[left] <= arr[keyi] && left < right){left++;}Swap(&arr[left], &arr[right]);}Swap(&arr[keyi], &arr[left]);return left;}//快速排序
void QuickSort(int* arr, int begin,int end)
{if (begin >= end)return;//走单趟int keyi = PartSort(arr, begin, end);//走【begin,keyi-1】和【keyi+1,end】QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);
}int main()
{int arr[] = { 6,1,10,7,5,3,4,9,2,8 };//快速排序QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1);Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

这里有个疑问：当left，right相遇时，我们是将key与left（相当于right）处的数相交换，从而使key找到正确的位置，但我们的规矩是key左边的数要比key对应的数要小，右边的数要比key要大，那这样交换，怎么能确认待交换这个数（也就是right和left相遇位置的数）要比key对应的位置小呐？？？

答案：这就要多亏与其中的一个小技巧，也就是当key在left处，我们就让right先走，当key在right处，我们就让left先走，当然key还有可能在中间，所以为了统一，我们写了三数取中函数GetMid（），这样就可以把合适的key放在left处，然后让right先走，这样写的好处是因为right和left相遇的情况有两种，如下：

①：当right动，left不动时，right去和left相遇：相遇位置是left处，但上一轮我们已经将right处（比key小的数）与left处（比key大的数）相交换了，所以该相遇处一定是比key处小的数。

②：当left动,right不动时，left去和right相遇：这种情况只能是right已经找到了比key小的数，然后停止，然后才让left移动，但是left向右移动过程中没有找到比key大的数，所以才会与right相遇，也就是说相遇处的数时由right找到的，所以相遇处的数一定会小于key处对应的数。

//未完待续