C语言数据结构与算法笔记（排序算法）

排序算法

基础排序

冒泡排序

核心为交换，通过不断进行交换，将大的元素一点一点往后移，每一轮最大的元素排到对应的位置上，形成有序。
设数组长度为N，过程为:

共进行N轮排序
每一轮排序从数组的最左边开始，两两元素进行比较，左边元素大于右边元素，就交换两个元素的位置，否则不变。
每轮排序都会将剩余元素中最大的一个推到最右边，下次排序就不再考虑对应位置的元素。

注意交换不能直接进行，需要中间元素。
实际上排序不需要N轮，N-1轮即可，最后一轮只有一个元素未排序。

// 冒泡排序
void BubbleSort(int arr[], int size)
{for(int i = 0; i < size-1 ;++i) // 减1是不考虑最后一次交换{for(int j = 0 ; j < size - i - 1; ++j ){if(arr[j] > arr[j+1]){int tmp = arr[j]; // 加入中间元素tmp进行交换arr[j] = arr[j+1];arr[j+1] = tmp;}}}
}int main()
{int size = 7;int arr1[] = {2,4,1,7,4,9,3};BubbleSort(arr1, size);for(int i = 0 ; i < size;++i){printf("%d ", arr1[i]);}
}

优化：如果整轮排序中没有出现任何交换，则说明数组是有序的，内层循环中加入标记
没有发生任何交换，则flag一定是1，数组有序

// 改进：没有出现交换则已经有序
void BubbleSort1(int arr[], int size)
{for(int i = 0 ; i < size - 1; ++i){_Bool flag = 1; // 加入标记for(int j = 0 ; j < size - 1 - i; ++j){   int tmp =arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}if(flag){break;}}
}

排序稳定性，大小相同的两个元素在排序前和排序后的先后顺序不变，则排序算法就是稳定的。比如以上的冒泡排序法只会在前者大于后者的情况下才会发生交换，不会影响到相等的两个元素。

插入排序

类似于斗地主的插牌。默认一开始只有第一张牌是有序的，剩余部分进行遍历，然后插到前面对应的位置上。
设数组长度为N

一共进行N轮排序
每轮排序会从后面依次选择一个元素，与前面已经处于有序的元素，从后往前比较，直到遇到一个不大于当前元素的元素，将当前元素插入到此元素的前面。
插入元素后，后续元素则全部后移一位。
当后面所有元素全部遍历完成，全部插入到对应位置之后结束排序。

// 插入排序
void InsertSort(int arr[], int size)
{for(int i = 1; i < size -1; ++i) // 从第2个元素开始{int tmp = arr[i], j = i;while (j > 0 && arr[j-1] > tmp) // 只要j>0并且前一个元素大于当前元素{arr[j] = arr[j-1]; // 交换前一个元素j--;}arr[j] = tmp;}
}
int main()
{int arr1[] = {2,1,8,5,6,4};InsertSort(arr1, 6);printArray(arr1, 6);     
}

改进：寻找插入位置上逐个比较，花费时间长，如果前面一部分元素已经是有序状态，可以考虑使用二分搜索算法来查找对应的插入位置，节省插入点的时间。

// 二分搜索法
int BinarySearch(int arr[], int left, int right, int target)
{int mid;while(left <= right){mid = (left + right) / 2;if(target == arr[mid]){return mid + 1;}else if (target < arr[mid]){right = mid - 1; // 目标值小于中间的值，往左边去找}else{left = mid + 1; // 往右边去找}}return left; // 二分划分范围，left就是插入的位置
}
// 改进的插入排序
void InsertSort1(int arr[], int size)
{for(int i = 0 ; i < size; ++i){int tmp = arr[i];int j = BinarySearch(arr,0,size-1,arr[i]); // 二分搜索查找插入的位置for( int k = i ; k > j; k--){arr[k] = arr[k-1]; // 往后移}arr[j] = tmp;}
}

算法稳定性，在优化前的插入排序，实际上是不断向前寻找一个不大于待插入元素的元素，相等时只会插入到其后面，不会修改相等元素的顺序；而改进后的二分搜索法，可能会将两个连续相等元素分割开来。

选择排序

每次都去后面找一个最小的放到前面。
设数组长度为N

共进行N轮排序
每轮排序会从后面的所有元素中寻找一个最小的元素，与已经排序好的下一个位置进行互换
进行N轮交换后，得到有序数组

// 选择排序
void SelectSort(int arr[], int size)
{for(int i = 0 ; i < size - 1; ++i) // N-1轮排序{int min = i ; // 记录当前最小的元素，默认是剩余元素中的第一个for(int j = i + 1; j < size;++j){if(arr[min] > arr[j]){min = j; }int tmp = arr[i]; // 找出最小元素之后，开始交换arr[i] = arr[min];arr[min] = tmp;}}
}
// 打印
void printArray(int arr[],int size)
{for(int i = 0 ; i < size;++i){printf("%d ", arr[i]);}
}
int main()
{int arr1[] = {2,9,6,8,3,6,5};SelectSort(arr1 , 7);printArray(arr1, 7);
}

改进：因为每次需要选一个最小的，不妨顺便选个最大的，小的往左边丢，大的往右边丢。

// 交换
void swap(int* a, int*b)
{int tmp = *a;*a = *b;*b = tmp;
}
// 优化的选择排序
void SelectSort1(int arr[], int size)
{int left=0, right = size - 1; // 假设左右排好序，往中间缩小while (left < right){int max = right, min = left;for(int i = left; i < right; ++i){// 同时找最大和最小的if(arr[i] < arr[min]){min = i;}if(arr[i] > arr[max]){max = i;}}swap(&arr[max], &arr[right]); // 先把大的换到右边// 大的换到右边之后，有可能被换出来的是最小的，需要判断以下// 如果遍历完最小的是当前右边排序的第一个元素// 将min换到那个位置if(min == right){min = max;}swap(&arr[min], &arr[left]);left++;right--;}  
}

稳定性：由于每次寻找的是最小的元素，向前插入时会发生交换操作，当存在两个连续相等元素，破坏了原有的顺序。不稳定的。

比较三种基础排序

冒泡排序（优化后）

最好情况时间复杂度：O(n)，本身是有序的，只需要一次遍历。
最坏情况时间复杂度：O(n^2)，倒序。
空间复杂度：O(1)，只需要一个变量存储需要交换的变量
稳定
插入排序
最好情况时间复杂度：O(n)，本身是有序的，插入的位置也是同样的位置，不变动任何元素
最坏情况时间复杂度：O(n^2)，倒序。
空间复杂度：O(1)，只需要一个变量存储抽出来的元素
稳定
选择排序
最好情况时间复杂度：O(n^2)，即使数组本身是有序的，每一轮还得将剩余部分依次找完才确定最小的元素
最坏情况时间复杂度：O(n^2)
空间复杂度：每一轮需要记录最小元素位置，空间复杂度为O(1)
不稳定

进阶排序

快速排序

快速排序是冒泡排序的进阶版，由于冒泡排序是对相邻元素进行比较和交换，每次只能移动一个位置，效率相对较低；而快速排序是从两端向中间进行，一轮就可将较小的元素交换到左边，较大的元素交换到右边。

实际上每一轮目的就是将较大的丢到基准右边，较小的丢到基准左边

一开始排序为整个数组
排序之前，以第一个元素作为基准
从最右边向左看，依次将每一个元素与基准元素进行比较，如果该元素比基准元素小，就与左边遍历位置上的元素（一开始为基准元素位置）进行交换，保留右边当前遍历的位置
交换后，转为从左边往右开始遍历元素，如果发现比基准元素大，则与之前保留右边遍历的位置上元素进行交换，同样保留左边当前遍历的位置
当左右遍历撞到一起，本轮快速排序完成，中间的位置元素就是基准元素
以基准位置为中心，划分左右两边，同样方式进行

代码实现

// 快速排序
void QuickSort(int arr[], int start, int end)
{if(start >= end) // 不满足初始位置则返回{return;}int left = start, right = end; // 定义两个指向左右两个端点的指针int pivot = arr[left]; // 预先确定基准点为左端第一个元素while (left < right){while(left < right && arr[right] >= pivot){right--;// 从右往左看}arr[left] = arr[right]; // 比基准值小就放到左边去while (left < right&& arr[left]  <= pivot){left++; // 从左往右看}arr[right] = arr[left]; // 比基准值大就放到右边arr[left] =pivot; //相遇位置即为基准存放的位置}QuickSort(arr, start , left-1); //划分基准左边QuickSort(arr, left+1, end); // 划分基准右边， 再次进行快速排序
}

测试

int main()
{int arr1[]= {9,3,6,3,4,8,1,2};QuickSort(arr1, 0 , 8);for(int i = 0; i < 8 ; ++i){printf("%d ", arr1[i]);}
}

双轴快速排序

快速排序的升级版，双轴快速排序，可对大数组进行。如果遇到数组完全倒序的情况
在这里插入图片描述
每一轮需要完整遍历整个范围，每一轮最大或最小的元素被推向两边，则此完全倒序情况快速排序退化为冒泡排序。为解决这种极端情况，再添加一个基准元素，使得数组可分为三段。

分为三段后，每轮双轴排序结束后对三段继续进行双轴快速排序。该适用于那些量比较大的数组。

首先取出首元素和尾元素作为两个基准，对其进行比较，若基准1大于基准2，先交换两个基准。
在这里插入图片描述
需要创建三个指针

从橙色指针所指元素开始进行判断，

小于基准1，那需要先将蓝色指针向后移，把元素交换到蓝色指针那去，然后橙色指针也向后移动
不小于基准1且不大于基准2，直接把橙色指针向前移动即可
大于基准2，需要丢到右边去，先将右边指针左移，不断向前找到一个比基准2小的，进行交换
橙色指针与绿色指针之间即为待排序区域

代码实现：

void swap(int* a, int*b)
{int tmp = *a;*a = *b;*b = tmp;
}void dualPivotQuickSort(int arr[], int start, int end)
{if(start >= end){return; // 结束条件}if(arr[start] > arr[end]) // 首尾两个基准比较{swap(&arr[start], &arr[end]); // 大的换到后面}int pivot1 = arr[start], pivot2 = arr[end]; // 取出两个基准元素int left = start, right = end, mid = left + 1; // 分三个区域，三个指针while (mid < right){if(arr[mid] < pivot1) // mid所指向元素小于基准1，需要放到最左边{swap(&arr[++left], &arr[mid++]); // 和最左边交换，left 和 mid向前移动}else if(arr[mid] <= pivot2) // 不小于基准1但小于基准2，在中间{mid++; // 本身在中间，向前移动以缩小范围}else // 右边的情况{while (arr[--right] > pivot2 && right > mid); // 先移动右边指针，需要右边位置来存放需要换过来的元素if(mid >= right){break; // 剩余元素找完，没有比基准2小的，可直接结束}swap(&arr[mid], &arr[right]); // 还有剩余元素，找到比基准2小的，直接交换   }} swap(&arr[left], &arr[start]); // 基准1与left交换，基准1左边元素都比其小swap(&arr[right],&arr[end]); // 基准2与right交换，基准2右边元素都比其大// 继续对剩下三个区域双轴快速排序dualPivotQuickSort(arr, start,left-1);dualPivotQuickSort(arr, left+1, right-1);dualPivotQuickSort(arr, right+1, end);
}

    dualPivotQuickSort(arr1, 0, 8);for(int i = 0; i < 8 ; ++i){printf("%d ", arr1[i]);}

希尔排序（缩小增量排序）

直接插入排序的进阶版，极端情况会出现让所有已排序元素后移的情况（比如刚好要插入的是一个特别小的元素），为解决这种问题，对整个数组按照步长进行分组，优先比较距离较远的元素。

步长是由一个增量序列，当增量序列一般使用 $\frac{n}{2}、\frac{n}{4}、\frac{n}{8}...、1$ 这样的序列。
设数组长度为N，详细过程为:

求出最初步长,n/2
整个数组按照步长进行分组，两两一组（n为奇数，第一组有三个元素）
分别在分组内插入排序
排序后，将步长/2，重新分组，重复上述步骤，直到步长为1，插入排序最后一遍结束

插入排序后，小的元素尽可能地向前走，缩小步长，4/2=2

代码实现

// 希尔排序
void shellSort(int arr[], int size)
{int delta = size / 2;while (delta >= 1) // 使用之前的插入排序，此时需要考虑分组{for(int i = delta; i < size; ++i) // 从delta开始，前delta个组的第一个元素默认是有序状态{int j = i, tmp = arr[i]; // 依然是把待插入的先抽出来while (j >= delta && arr[j - delta] > tmp) {// 需要按步长往回走，所以是j-delta，j必须大于等于delta才可以,j-delta小于0说明前面没有元素arr[j] = arr[j - delta];j -= delta;}arr[j] = tmp;}delta /= 2; // 分组插排结束之后，再计算步长}
} 
int main()
{int arr[] = {3,5,7,2,9,0,6,1,8,4};shellSort(arr, 10);for(int i = 0 ; i < 10; ++i){printf("%d ", arr[i]);}
}