• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[数据结构与算法]—— * 快速排序 *

互联网 diligentman 2小时前 3次浏览

今天小玄为大家带来平时代码时常用的一种排序方法——快速排序

[数据结构与算法]—— * 快速排序 *

算法简介

快速排序(Quick Sort)是在冒泡排序的基础上演变而来的,实际上是冒泡排序 递归分治法。

快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移到数列的一边,比它小的元素移到数列的另一边,从而把数列拆解成了两个部分。

具体流程如下:

  1. 通过分割将对象局部数组分割成前后两个局部数组(Divide)
  2. 对前半部分数组执行quickSort(Solve)
  3. 对后半部分数组执行quickSort(Solve)

算法解析 

我们实现要确定分界点x – 取q【(l + r) / 2】 或者是    随机值

[数据结构与算法]—— * 快速排序 *

然后使用双指针进行操作 -—— L R 

我们确保在分界点左边的数都小于等于x

在分界点右边的数都大于x

L++ R–,直到发现L找到了>x的数,R找到了小于等于x的数,将两个数进行交换

[数据结构与算法]—— * 快速排序 *

 持续这样的过程直到两个指针相遇为止  —— L >=  R

接下来我们只要将这样的过程持续递归进行下去即可。


代码思路

一,“暴力处理”

  1. 创建两个数组 a[] b[]
  2. 创建存储数组 q[] 
    1.  q[l ~ r] (如果 q[i]  <= x  ——  x -> a[])  
    2.  q[l ~ r] (如果 q[i]  > x  ——  x -> b[])
  3. 结果输入
    1. ​​​​​​​a[]  -> q[]         
    2. b[]  -> q[]

[数据结构与算法]—— * 快速排序 * 

二,优美的解法(按上述思路在原数组进行操作)

 [数据结构与算法]—— * 快速排序 *

大致思路如上图所示。


代码实现 

C语言

#include <stdio.h>

int arr[1000],n;   //定义全局变量,这两个全局变量需要在函数中使用

void quicksort(int left,int right)
{
    int i = 0;
    int j = 0;
    int t = 0;
    int temp = 0;
    
    if(left > right)
        return;
    
    temp = arr[left];  //temp中存的是基准数
    i = left;
    j = right;
    while(i != j)
    {
        //顺序很重要,从右往左找
        while(arr[j] >= temp && i < j)
            j--;
        while(arr[i] <= temp && i < j)
            i++;
        
        //交换两个数在数组中的位置
        if(i < j) //当哨兵i和哨兵j没有相遇的时候
        {
            t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
        
        //最终将基准数归位
        arr[left] = arr[i];
        arr[i] = temp;
        
        quicksort(left,i-1);
        quicksort(i+1,right);
        return;
}

int main()
{
    int i = 0;
    int j = 0;
    scanf("%d",&n);
    for(i = 0;i < n ;i++)
    {
        scanf("%d",&arr[i]);
    }
   
    quicksort(0,n-1);
    
    for(i = 0;i < n - 1;i++)
        printf("%d ",arr[i]);
     printf("%d",arr[n - 1]);
    return 0;
}

c++

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[],int l,int r)
{
    if(l >= r) return;
    
    int i = l - 1,j = r + 1, x = q[(l + r) >> 1];
    while(i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&q[i]);
    
    quick_sort(q,0,n - 1);
    
    for(int i = 0;i < n;i++) printf("%d ",q[i]);
    
    return 0;
}

延伸讨论

 快速排序和归并排序一样基于分治法 但其执行partition进行分割时就已经在原数组中完成了排序,因此不需要归并排序中那样手动的合并处理。

快速排序在分割的过程中会交换不相邻元素,因此属于不稳定的算法。另一方面,归并排序需要O(n)的外部储存空间,快速排序并不需要用到额外内存。也就是说,快速排序是一种原地算法(内部排序)

在分割时如果能恰好取到中间值,那么整个过程大致和归并排序一样分为log2n层。快速排序的时间复杂度是O(logn),是一般情况下最高效的排序算法。不过如果我们选择固定的方式来选择基准的话,在处理某些数据(例如已经排序完的数据)时效率会大打折扣,最复杂的情况甚至达到O(n2).不仅如此,某些顺序的数据可能会让递归深度过深,最终导致栈溢出。一般情况下,我们需要在选择基准的方式上多花费心思,比如随机选择,或者任选出几个之后取中间值也可。


今天的文章到此就结束啦,如果觉得对你有帮助的话,请给小玄:

[数据结构与算法]—— * 快速排序 * 

[数据结构与算法]—— * 快速排序 * 

 


程序员灯塔
转载请注明原文链接:[数据结构与算法]—— * 快速排序 *
喜欢 (0)