经典排序算之快速排序

2016.8.17改

快速排序的实现

伪代码：
Quicksort(A[l...r])
    if (l < r)
        s<-partition(A[l...r])
        Quicksort(A[l...s-1])
        Quicksort(A[s+1...r])
HoarePartition(A[l...r])
    //以第一个元素为中轴对字数组进行划分
    p <- A[l]
    i <- l;j <- r+1
    repeat
         repeat i <- i+1 until A[i] >= p
          repeat j <- j-1  until A[j] <= p
          swap(A[i],a[j])
    until i >= j
    swap(A[i],A[j])//当i >= j撤销最后一次交换
    swap(A[l],A[j])
    return j
c语言代码如下：

#include<stdio.h>
#include<stdlib.h>
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int partition(int *a,int lo,int hi){
    int i = lo,j = hi+1;
    int v = a[lo];
    int temp = 0;
    while (1){
        while (a[++i] < v) if (i == hi) break;
        while (a[--j] > v) if (j == lo) break;
        if (i >= j) break;
        swap(temp,a[i],a[j]);
    }
    swap(temp,a[lo],a[j]);
    return j;
}
void quicksort(int *a,int lo,int hi){
    if (lo >= hi) return;
    int s = partition(a,lo,hi);
    quicksort(a,lo,s-1);
    quicksort(a,s+1,hi);

}
int main()
{
    printf("请输入数组元素个数len = ");
    int len = 0;
    scanf("%d",&len);
    int a[len];
    int i = 0;
    for (i = 0;i < len;i++){
         printf("请输入第%d个:"i+1);
         scanf("%d",&a[i]);//注意&
    }
    quicksort(a,0,len-1);
    for (i = 0;i < len;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;

}

寻找最小的k个数;

#include<stdio.h>
#include<stdlib.h>
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int partition(int *a,int lo,int hi){
    int i = lo,j = hi+1;
    int v = a[lo];
    int temp = 0;
    while (1){
        while (a[++i] < v) if (i == hi) break;
        while (a[--j] > v) if (j == lo) break;
        if (i >= j) break;
        swap(temp,a[i],a[j]);
    }
    swap(temp,a[lo],a[j]);
    return j;
}
int quicksort(int *a,int lo,int hi,int k){
    //if (lo >= hi) return;
    int s = partition(a,lo,hi);
    if (s == lo+k-1) return s;
    else if (s > lo+k-1) quicksort(a,lo,s-1,k);
    else quicksort(a,s+1,hi,lo+k-1-s);

}
int main()
{
    printf("请输入数组元素个数len = ");
    int len = 0;
    scanf("%d",&len);
    int a[len];
    int i = 0;
    for (i = 0;i < len;i++){
         printf("请输入第%d个:",i+1);
         scanf("%d",&a[i]);//注意&
    }
    int s = quicksort(a,0,len-1,5);
    for (i = 0;i <= s;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;

}

时间复杂度O(n)