目录一.快速排序1).快排的介绍3).lomuto前后指针法4).非递归快排二.选择排序一.快速排序1).快排的介绍快速排序是基于分治思想的经典交换排序算法它选定一个元素作为基准值通过双指针遍历将数组划分为两部分使基准左侧元素全部小于等于它、右侧元素全部大于等于它再递归对划分得到的左右子区间重复上述操作不断缩小待排序范围最终得到整体有序的数组平均时间复杂度为 O (nlogn)最坏情况下可达 O (n²)属于不稳定排序。2).Hoare快排思路选取区间最左侧下标 keyi 作为基准位置将left 指针移到基准的下一位开始遍历在外层left right循环下使 right先移动right 从区间右端向左遍历当元素严格大于基准值时持续左移直到找到小于或等于基准的元素停下。接着 left 从左向右遍历当元素严格小于基准值时持续右移直到找到大于或等于基准的元素停下若此时 left 和 right 尚未相遇就交换两个指针指向的数组元素同时使 right -- left 当外层循环结束说明 right left此时right 指向的就是基准元素应当存放的最终位置交换原基准位置 keyi 与 right 位置的元素将基准放置到它的有序位置最后返回 right 下标供外部递归函数划分左右子区间继续排序。为什么 right / left 移动时判断条件要严格大于 / 小于基准值原因是如果条件为大于等于 / 小于等于并且如果需要排序的数据相同或排列有序算法的时间复杂度会从O(n * logn)变为O(n ^ 2)大大提升所需时间。借用网络流传图片理解代码如下://hoare版本 int _QuickSort1(int* arr, int left, int right) { int keyi left; left; while (left right) { //right从右往左走找比基准值要小的 while (left right arr[right] arr[keyi]) { right--; } //left从左往右走找比基准值要大的 while (left right arr[left] arr[keyi]) { left; } //right left if (left right) { Swap(arr[left], arr[right--]); } } Swap(arr[keyi], arr[right]); return right; } //快速排序 void QuickSort(int* arr, int left, int right) { if (left right) { return; } //找基准值 int keyi _QuickSort(arr,left,right); //left keyi right //左序列[left,keyi-1] 右序列[keyi1,right] QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi 1, right); }3).lomuto前后指针法.lumoto前后指针法与之前顺序表算法题中的双指针思想异曲同工如果掌握双指针对lomuto前后指针法的理解就比较容易了prev站岗cur 探路。思路选取区间最左侧元素作为基准设置两个指针prev 初始指向基准位置cur 从基准的下一个位置开始向后遍历cur 不断向右遍历一旦遇到小于基准值的元素就先将 prev 向后移动一位如果 prev 和 cur 不重合则交换两个指针指向的数据把小元素往区间左侧聚拢当 cur 遍历完整个区间后所有小于基准的元素都集中在 cur 的左边最后交换基准位置与 prev 位置的元素基准就落到它最终有序的位置函数返回 prev 下标用于递归划分左右子区间。借用网络流传图片理解代码如下//lomuto前后指针法 int _QuickSort(int* arr, int left, int right) { int keyi left; int prev left, cur prev 1; while (cur right) { if (arr[cur] arr[keyi] prev ! cur) { Swap(arr[prev], arr[cur]); } cur; } Swap(arr[keyi], arr[prev]); return prev; } //快速排序 void QuickSort(int* arr, int left, int right) { if (left right) { return; } //找基准值 int keyi _QuickSort(arr,left,right); //left keyi right //左序列[left,keyi-1] 右序列[keyi1,right] QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi 1, right); }4).非递归快排非递归快排要借助数据结构栈/队列来存放数据本文采取数据结构栈。思路首先初始化栈将待排序区间的left和right先后入栈只要栈不为空不断取出栈顶元素 begin 和end 对[begin , end ]区间执行 Lomuto 前后指针分区得到基准元素的最终下标keyi分区完成后会产生左右两个子区间[begin, keyi‑1]和[keyi1, end]只有子区间内元素数量大于 1 时才将区间边界压入栈中避免处理无效区间循环不断取出栈中的区间重复分区操作直到栈为空代表全部区间处理完毕最后销毁栈完成排序。代码如下//非递归版本的快速排序——栈 void QuicSortNoR(int* arr, int left, int right) { ST st; StackInit(st); StackPush(st, left); StackPush(st, right); while (!StackEmpty(st)) { //取栈顶两次 int end StackTop(st); StackPop(st); int begin StackTop(st); StackPop(st); //[begin,end]找基准值 int keyi begin; int prev begin, cur prev 1; while (cur end) { if (arr[cur] arr[keyi] prev ! cur) { Swap(arr[prev], arr[cur]); } cur; } Swap(arr[keyi], arr[prev]); keyi prev; //begin keyi end //左序列[begin,keyi-1] 右序列[keyi1,end]; if (keyi 1 end) { StackPush(st, keyi 1); StackPush(st, end); } if (begin keyi - 1) { StackPush(st, begin); StackPush(st, keyi - 1); } } StackDestroy(st); }二.选择排序选择排序是一种简单直观的排序算法。它的工作原理是第一次从待排序的数据元素中选出最小(或最大)的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找最小(大)元素,将其放到已排序的序列的末尾。以此类 推,直到全部待排序的数据元素的个数为零。借用网络流传图片理解代码如下void SelectSort(int* arr, int n) { int begin 0, end n - 1; while (begin end) { int maxi begin; int mini begin; for (int i begin1; i end; i) { if (arr[i] arr[mini]) { mini i; } if (arr[i] arr[maxi]) { maxi i; } } //mini begin //maxi end if (maxi begin) { maxi mini; } Swap(arr[mini], arr[begin]); Swap(arr[maxi], arr[end]); begin; end--; } }三.插入排序直接插入排序把数组分为已排序区间和未排序区间初始时第一个元素作为已排序区间后面全部元素属于未排序区间依次取出未排序区间的第一个元素作为待插入元素向前遍历已排序区间把比待插入元素大的元素向后挪动腾出位置找到合适的空位后将待插入元素放入不断扩大有序区间直到全部元素处理完成整个数组就变为有序它属于稳定排序最好时间复杂度O(n)最坏和平均时间复杂度O(n^2)。具体步骤如下从第二个元素开始将其保存在一个临时变量中。向前遍历已排序序列如果当前元素大于临时变量将当前元素后移。如果找到小于或等于临时变量的位置将临时变量插入到该位置。重复步骤 1 到 3直到所有的元素都被插入到正确的位置。借助网络流传图片理解代码如下//直接插入排序 void InsertSort(int* arr, int n) { for (int i 0; i n - 1 ; i) { int end i; int tmp arr[end 1]; while (end 0) { if (arr[end] tmp) { arr[end 1] arr[end]; end--; } else { break; } } arr[end 1] tmp; } }四.希尔排序希尔排序是对直接插入排序的优化算法它先设置一个gap间隔按照 gap 把数组分成若干组对每一组分别执行直接插入排序之后不断缩小 gap 的值重复分组插入排序当 gap 缩减为 1 时就等价于普通的直接插入排序此时数组已经基本接近有序少量元素移动即可完成整体排序希尔排序打破了直接插入排序一次只能移动一个位置的局限让远距离的元素可以快速归位提升排序效率它是不稳定排序最坏时间复杂度为 O (n²)。具体代码逻辑如下初始化间隔 gap 为数组长度 n。当 gap 大于 1 时进行排序循环。更新 gap 的值为 gap 除以 3 后再加 1这是希尔排序中推荐的一个常用间隔序列。遍历数组从索引 0 到索引 n - gap - 1。在每个遍历位置记录当前索引为 end同时记录 end gap 处的元素值为 tmp。在当前位置进行比较和移动操作如果当前位置的元素大于 tmp则将当前元素后移 gap 个位置并将 end 减去 gap。如果当前位置的元素小于等于 tmp则跳出内层循环。将 tmp 插入到最终位置 end gap 处。循环结束后数组中的元素按照指定的间隔有序排列。代码如下//希尔排序 void ShellSort(int* arr, int n) { int gap n; while (gap 1) { gap gap / 3 1;//3 2 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; } } }