基本上学过编程的人都知道排序算法,而最常用的排序算法就是冒泡排序了,如下:

void swap(int *a,int i,int j){
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

void bubble_sort(int *a,int len){
    int max = len-1;
    int i,j;
    for(i=0;i<max;i++){
        for(j=0;j<max-i;j++){
            if(a[j+1]<a[j]){
                swap(a,j,j+1);
            }
        }
    }
}

但是只要测试过的同学都知道,这种算法的效率并不高,对于比较大的数组基本上是无能为力滴(会超时),所以此时,我们便需要一个更加快速的排序算法:快速排序

听这名字就感觉很nb对不对,接下来我们就来讲一下快速排序的原理:

就以以下数组a[n]为例

n=01234567891011
3262395928484

我们以a[0]为基准数,需要将比3小的数据放到左侧,比3大的数据放到右侧,具体的实现方法:

定义value = a[0] , i = 0 , j = 11;

此举目的可以理解为在a[0]的位置“挖一个坑”,接下来可以让其它的数据填充进来

接下来,我们从右向左寻找a[j] <= value,将其“从坑中挖出”,填入a[i]的位置

那么在原本a[j]的位置就又有了一个“坑”,我们再从左边开始寻找a[i] >= value,将其“从坑中挖出”,填入a[j]的位置

如此反复,直至i == j时,将value填入坑中,大功告成

此时数组变为

n=01234567891011
2232395968484

根据以上的思路,可以写出程序

int sort(int s[], int l, int r){
  int i = l, j = r;
  int x = s[l];
  while (i < j)
  {
    while(i < j && s[j] >= x) 
      j--;  
    if(i < j) 
    {
      s[i] = s[j];
      i++;
    }
    while(i < j && s[i] < x)
      i++;  
    if(i < j) 
    {
      s[j] = s[i];
      j--;
    }
  }
  s[i] = x;
 
  return i;
}

递归加上

void quick_sort(int s[], int l, int r){
  if (l < r)
    {
    int i = sort(s, l, r);
    sort(s, l, i - 1);
    sort(s, i + 1, r);
  }
}

整合一下

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

完工

最后,据说使用随机生成的基准数能提升排序速度,感兴趣的同志们可以试试

打赏 赞(1)
支付宝二维码图片

支付宝扫描二维码打赏

发表评论

电子邮件地址不会被公开。

Scroll Up