【经典算法复习】快速排序的应用
快速排序算法是面试和考研中经常考的一种算法，但题目中通常不会直接要求你写出快速排序算法，比较常见的是提出一个排序要求，然后让你自己选择合适的排序算法实现。
这种考查方式要求对常见的几种排序算法的思想都要了解才能做出选择，这篇文章我们就来总结一下快速排序算法常见的应用场景。
快速排序的算法思想
快速排序是对冒泡排序的一种改进，它的基本思想是从待排数据中选择一个元素作为基准元素，通过一趟排序将待排序数据分成两部分，其中一部分的所有数据比基准元素都要小，另一部分比基准元素都要大；然后按照这种方法对两部分数据分别排序，直到整个序列成为一个有序数列，这是一个递归的过程。
快速排序的代码实现
使用首尾指针(i,j)遍历法，从数组的两端交替地向中间扫描，如果最终要求实现从小到大的排列顺序，那么j指针从右端向左搜寻比基准元素小的数保存到a[i]，i指针从左端向右搜寻比基准元素大的数保存到a[j]。
void quickSort(int a[], int low, int high){
if (low >= high)
return;
int i=low,j=high;
int temp=a[i];
//取第一个元素作为基准元素,保存到temp,a[i]空出来
while(i<j){
while(i<j&&a[j]>=temp)
--j;
a[i]=a[j];
while(i<j&&a[i]<=temp)
++i;
a[j]=a[i];
}
a[i]=temp;
//将基准元素放到a[i]这个分隔点上,代码至此,完成了一趟遍历
quicksort(a,low,i-
1);
//递归对左部分数据进行排序
quicksort(a,i+
1,high);
//递归对右部分数据进行排序
}
快速排序的应用场景
场景一：有一组非零整数，写一个算法将负数放在左边，正数放在右边。
分析：这个题目我们就可以借鉴快速排序的基准元素将数据分隔成两部分的方法，取基准元素为整数0。
代码实现：
void sortArray(int a[], int n)
{
int i=
0, j=n-
1, temp=a[
0];
//第一个元素保存到temp,将a[i]空出来
while(i<j){
while(i<j&&a[j]>
0)
//基准元素为整数0
--j;
a[i]=a[j];
while(i<j&&a[i]<
0)
//基准元素为整数0
++i;
a[j]=a[i];
}
a[i]=temp;
//运行到这里时，a[i]这个分割点上仍然是空的，可以放置任何元素，所以不管temp中存的是正数还是负数都可以放在此。
//因为题目只要求将正数和负数分成两部分，不要求排序，所以快速排序的一趟遍历就可以满足题目要求。
}
类似的题目还可以这样出，给一组整数，将奇数放在左边，偶数放在右边。
场景二: 给一数组a[1...n]，选出其中第K小(大)的那个数。
int selectTopK(int a[], int low, int high, int K)
{
int i=low,j=high;
int temp=a[i];
while(i<j){
while(i<j&&a[j]>=temp)
--j;
a[i]=a[j];
while(i<j&&a[i]<=temp)
++i;
a[j]=a[i];
}
a[i]=temp;
if(i==K-
1)
//数组下标从零开始
return temp;
else
if(i>K-
1)
return selectTopK(a, low, i-
1, K);
else
return selectTopK(a, i+
1, high, K);
}
·end·
—如果喜欢，快分享给你的朋友们吧—
长按二维码