【数据结构】排序（上）

个人主页~

堆排序看这篇~
还有这篇~

---

一、排序的概念及应用

1、概念

排序就是按照某一关键字递增和递减排列起来的操作
排序在生活中非常常用，成绩、排行等等一切跟数字字母等有关的都能够排序

2、常见的排序算法

常见的排序算法有
插入排序：直接插入排序，希尔排序
选择排序：选择排序，堆排序
交换排序：冒泡排序、快速排序
归并排序：归并排序

二、常见排序的实现

1、直接插入排序

（1）基本思想

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

（2）代码实现

//我们看做一个一个插入
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){//从0到end都有序，tmp插入排序int end = i - 1;//end存储插入前的最后一个元素的下标，也就是第i-1个数据int tmp = a[i];//tmp是插入的数据，也就是第i个数据while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}//如果前边比后边大，就交换并且--end，继续向前比较else{break;//直到后边比前边大}}a[end + 1] = tmp;//将此时end+1下标的位置赋值tmp，后边的数据全都往后移了一位}
}

封装一个打印数组的函数

void ArrPrint(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}

（3）时间复杂度

如果按照最坏的情况：
第一次排不需要比较
第二次需要比较一次
第三次需要比较两次
…
第N次需要比较N-1次
F(N)=0+1+2+3+…+N-1 = (N-1)*(N)/2
所以直接插入排序的最坏时间复杂度为O(N^2)
最好时间复杂度就是有序数组O(N)
所以直接插入排序是介于它们之间的，这才有了希尔排序这种优化算法，降低了时间复杂度

（4）空间复杂度

没有占用额外空间，O(1)

2、希尔排序

（1）基本思想

希尔排序可以说是高级的直接插入排序，它是希尔通过观察和实践在直接插入排序的基础上进行算法优化，将时间复杂度降低
希尔排序分为两步：
第一步：预排序，是将无序的数组排序至接近有序
第二步：直接插入排序
当gap越小越接近有序，gap越大预排序的速度会更快
当gap为1时，就是直接插入排序
简单来说希尔排序就是粗排后细排

（2）代码实现

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//分为三组，最后加一可以保证最后一次的while循环gap等于1，相当于直接插入排序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;}elsebreak;}//同直接插入排序，差别是分了组，每次要对比的数字的下标差了gapa[end + gap] = tmp;}}
}

（3）时间复杂度

希尔排序的时间复杂度并不好计算，因为gap的取值很多，我们没办法通过简单的计算来得出结果，这是一个数学上的难以解答的问题，资料中显示，它的时间复杂度在O(n^1.25)到O(1.6*n ^1.25)之间，我们粗略表示成O(n ^1.3)

（4）空间复杂度

没有占用额外空间，O(1)

3、选择排序

（1）基本思想

遍历数组，每一次将最大和最小的数据挑出来放到数列的起始和末尾位置，知道所有元素全部排完
这是一种超级慢的排序方式，实际使用中很少用

（2）代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;}void SelectSort(int* a, int n)
{int right= n - 1;//定位到数组最后一个元素下标int left = 0;//定位到数组第一个元素下标while (left < right){int min = left;//先将left作为最开始的最小值int max = right;//先将right作为最开始的最大值for (int i = left; i <= right; i++){if (a[i] < a[min])min = i;if (a[i] > a[max])max = i;}//在left和right之间选出最大和最小的数Swap(&a[left], &a[min]);//交换a[left]与a[min]if (left == max)max = min;//这里注意，当最大值与left重叠时，将位置修正再交换Swap(&a[right], &a[max]);left++;right--;}
}

（3）时间复杂度

它的时间复杂度就是等差数列求和，可以很容易的看出来它的时间复杂度为O(N^2)

（4）空间复杂度

没有占用额外空间，O(1)

4、堆排序

在之前的文章中有详细的解释，我们可以来到二叉树-堆文章中来详细了解

（1）基本思想

利用堆的特性，即小堆堆顶最小，大堆堆顶最大的性质，来进行升序或降序排序

（2）代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustDown(int* a, int n,int parent)
{int child = parent * 2 + 1;while(child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}//调出值较大的那个孩子if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//交换后让孩子当爹，使其跟它的孩子比较elsebreak;}
}void HeapSort(int* a, int n)
{//parent = (child-1) / 2，i的初始值是最后一个元素的父节点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--;}
//每次调整都会将最大的一个数放在当前调整范围的最后一个位置，而调整范围的最后一个位置每次都会向前一个，直到成为升序数组
}

（3）时间复杂度

在前面链接中的文章中我们计算过它的时间复杂度，O(N*log₂N)

（4）空间复杂度

没有额外申请空间，O(1)

5、冒泡排序

（1）基本思想

冒泡排序是我们初识C语言时的接触到的第一个排序方式，也可以说是最鸡肋的排序方式，简单易懂但效率很低，就是两两元素相互比较，大的往后移动，遍历一遍下来最大的就到最后了，以此类推实现排序
这里我就不过多解释了

（2）代码实现

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

（3）时间复杂度

相当于等差数组求和，n-1 + n-2 + … + 1
F(N) = (N-1+1)/2 * N/2
时间复杂度为O(N^2)

（4）空间复杂度

没有占用额外空间，空间复杂度为O(1)

6、快速排序

（1）基本思想

任取待排序序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素小于基准值，右子序列中所有元素大于基准值，然后在左右子序列中重复该过程，直到排序完成
这里我们每一次取的基准值都是左数第一个元素

（2）代码实现

①hoare版本

int PartSort1(int* a, int left, int right)
{int keyi = left;//将最左边的元素作为关键元素，即基准值，记录它的下标while (left < right){while (left < right && a[keyi] <= a[right]){right--;}while (left < right && a[keyi] >= a[left]){left++;}Swap(&a[left], &a[right]);
//左右两边向中间逼近，在右边找到小于基准值的数字，在左边找到大于基准值的数字，两者交换}Swap(&a[keyi], &a[left]);//循环出来之后，说明left与right相遇了，也就是说此时的这个位置左边的数字全部比基准值小，右边的数字都比基准值大，将这个位置的数字与基准值位置的数字交换位置return left;//将此时的基准值返回
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort1(a, left, right);//将区间分成三个部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

②挖坑法版本

int PartSort2(int* a, int left, int right)
{int key = a[left];//存下坑里的数字int hole = left;//把最左边的位置作为坑while (left < right){while (left < right && a[right] >= key)right--;//找到a[right] < key的位置跳出循环a[hole] = a[right];hole = right;//把这个位置挖新坑，将坑里的值存起来while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;//右边挖完左边挖，左边找大于基准值的}a[hole] = key;//将最开始存下来的基准值填到此时剩下的坑里return hole;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort2(a, left, right);//将区间分成三个部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

③前后指针版本

int PartSort3(int* a, int left, int right)
{int prev = left;//初始前指针为最左边的元素int cur = left + 1;//初始后指针为前指针的后一个元素int keyi = left;//存下前指针的下标作为基准值下标while (cur <= right){while (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);
//如果后指针指向的数字大小小于基准值，并且前指针的后一个指针不为后指针，那么前后指针指向位置的值交换
//当后指针指向的值小于基准值时，前指针都会往后走（这里的知识涉及到逻辑语句的短路）cur++;//后指针往后走}Swap(&a[prev], &a[keyi]);keyi = prev;//最后前指针所指向元素的大小一定大于基准值，将他们交换，此时的基准值左边除了第一个都比它小，右边都比它大return keyi;
}void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = PartSort3(a, left, right);//将区间分成三个部分：keyi，keyi左，keyi右QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);//对剩下的区间继续排序
}

（3）时间复杂度

快速排序是一种类二叉树类型的排序，所以它的时间复杂度为O(N*log₂N)，计算方法同二叉树

（4）空间复杂度

递归创建类二叉树，空间复杂度为O(log₂N)

---

下期再见~