【排序算法】快速排序

快速排序（Quick Sort）是一种常用的算法>排序算法，它采用分而治之的策略来对一个序列进行排序。快速排序的基本思想是选择一个基准元素（通常是序列中的第一个元素），然后将序列中的其他元素分为两个子序列，一个子序列中的所有元素都比基准元素小，另一个子序列中的所有元素都比基准元素大。然后对这两个子序列递归地进行快速排序，直到所有子序列都变为有序的，此时整个序列也就变得有序了。

快速排序的步骤如下：

选择基准：在数据集之中，选择一个元素作为"基准"（pivot）。
分区操作：将数组进行分区（partition），将小于基准的元素移到基准的左边，将大于基准的元素移到基准的右边。分区完成后，基准元素所处的位置就是最终排序后它的位置。
递归排序：递归地将小于基准元素的子序列和大于基准元素的子序列排序。

快速排序的效率在平均状况下是非常高的，其时间复杂度为O(n log n)，但最坏情况下的时间复杂度为O(n^2)。最坏情况通常是由于基准元素的选择不当造成的，例如序列已经是有序的情况下，选择第一个元素作为基准。为了提高效率，有时会采用随机选择基准或者选择中位数作为基准的策略。

快速排序是一个不稳定的算法>排序算法，因为在排序过程中，相等的元素的顺序可能会改变。

1. 找枢轴

#include <stdio.h>
void quickSort(int * p,int low,int high)
{int flag = p[low];while(low < high){while(p[high]>= flag && low <high)high--;if(low <high){p[low]=p[high];low ++;}while(p[low]<=flag && low <high)low++;if(low <high){p[high]=p[low];high--;}}p[low]=flag;printf("枢轴位置为:%d\n",low);
}void showArr(int *p,int n)
{int i;for(i = 0;i < n;i++){printf("%d ",p[i]);}printf("\n");
}int main(int argc, const char *argv[])
{int b[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};showArr(b,15);quickSort(b,0,14);showArr(b,15);return 0;
}

2.快速排序最终版

#include <stdio.h>
//low 和 high 代表数组中进行快排区间段的起始和终止下标
void quickSort(int* p, int low, int high)
{//1.将区间段的起始位置元素作为镖旗int i = low;//用i保存low的值int j = high;//用j保存high的值int flag = p[low];//2.找枢轴while(low < high)//当循环结束的时候 low == high,此时low和high的值也就是下标位置,就是枢轴{//(1)从右向左扫描,只要p[high] >= flag,就执行high--while(p[high] >= flag && low < high)high--;if(low < high){//(2)循环结束,说明遇到了p[high] < flag,需要将较小的数p[high],移动到左边p[low] = p[high];//(3)移动过来之后,从左向右扫描,执行low++,因为刚移动过来的,没必要再和flag比较low++;}//(4)继续从左向右扫描,只要p[low] <= flag,就执行low++while(p[low] <= flag && low < high)low++;if(low < high){//(5)上面的循环结束后,说明遇到了p[low] > flag,遇到较大的数,需要移动到右侧p[high] = p[low];//(6)移动之后,从右向左扫描,执行high--,因为刚移动过来的,没必要再和flag比较high--;}}//3.将flag放在枢轴位置p[low] = flag;//或者 p[high] == flagprintf("枢轴是%d %d\n",low,high);//low和high的值相等//4.递归对枢轴的左侧和右侧进行同样的操作if(i < low-1)quickSort(p, i, low-1);//对起始下标到枢轴-1进行递归if(low+1 < j)quickSort(p, low+1, j);//对枢轴+1到终止下标进行递归
}void showArray(int* p, int n)
{int i;for(i = 0; i < n; i++){printf("%d ",p[i]);}printf("\n");
}int main(int argc, const char *argv[])
{int a[8] = {32, 2, 54, 6, 78, 23, 17, 76};showArray(a,8);quickSort(a,0,7);showArray(a,8);return 0;
}

结语

以上结束快速排序的基本使用，本次代码分享到此结束，后续还会分享数据结构与算法的有关知识。最后的最后，还请大家点点赞，点点关注，谢谢大家！