快速排序算法 快速排序算法在最好情况下的时间复杂度为

干货来了，干货来了，清华北大的程序员，甚至对每一个程序来说都要掌握的排序算法，下面我们来讲解下快速排序算法。

快速排序(quick sort)是由C.A.R Hoarse提出的一种排序算法，它是冒泡排序的一种改进算法。由于快速排序算法元素之间的比较次数较少，速度较快，因而得名快速排序。在各种内部排序方法中，快速排序被认为是目前最好的一种排序方法。

快速排序算法的基本思想是：在当前的排序序列(k1,k2,…kn)中任意选取一个元素，把该元素称为基准元素或支点，把小于等于基准元素的所有元素都移到基准元素的前面，把大于基准元素的所有元素都移到基准元素的后面，这样使得基准元素所处的位置恰好就是排序的最终位置，并且把当前参加排序的序列划分为前后两个子序列。

源代码：

#include "stdio.h"
void swap(int *a,int *b)
{							/*序列中元素位置的交换*/
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}
void quicksort(int k[], int s,int t)
{							/*快速排序*/
    int i,j;
    if(s<t){
        i = s;
        j = t+1;
        while(1){
            do i++;
            while(!(k[s]>=k[i] || i==t));		/*重复执行i++操作*/
            do j--;
            while(!(k[s]<=k[j] || j==s));		/*重复执行j--操作*/
            if(i<j)
                swap(&k[i],&k[j]);				/*交换k[i]和k[j]的位置*/
            else
                break;
        }
        swap(&k[s],&k[j]);				/*交换基准元素与k[j]的位置*/
        quicksort(k,s,j-1);				/*递归排序基准元素前面的子序列*/
        quicksort(k,j+1,t);				/*递归排序基准元素后面的子序列*/
    }
}
main()
{
    int k[10]={2,5,6,3,7,8,0,9,12,1} , i;
    printf("The orginal data array is\n") ;
    for(i=0;i<10;i++)						/*显示原序列之中的元素*/
        printf("%d ",k[i]);
    quicksort(k,0,9);						/*快速排序*/
    printf("\nThe result of quick sorting for the array is\n");
    for(i=0;i<10;i++)						/*显示排序后的结果*/
        printf("%d ",k[i]);
    getche();
}

运行结果

源代码：
typedef int keytype;
void adjust(keytype k[],int i,int n)
{
    int j;
    keytype tmp;
    tmp = k[i];
    j = 2 * i;
    while(j<=n)
    {
        if(j<n && k[j]>k[j+1])
        {
            j++;					/* j为i的左右孩子中较小孩子的序号*/
        }
        if(tmp<=k[j])
        {
            break;				/*tmp为最小的元素，则不需要元素的交换*/
        }
        k[j/2] = k[j];			/*交换元素位置*/
        j = 2 * j;
    }
    k[j/2] = tmp;
}
void heapsort(keytype k[],int n)
{
    int i;
    keytype tmp;
    for(i=n/2;i>=1;i--)
    {
        adjust(k,i,n);			/*将原序列初始化成一个小顶堆*/
    }
    for(i=n-1;i>=1;i--)
    {
        tmp = k[i+1];			/*调整序列元素*/
        k[i+1] = k[1];
        k[1] = tmp;
        adjust(k,1,i);
    }
}
main()
{
    int i,k[11]= {-111,5,2,12,6,9,0,3,6,15,20};
        printf("The orginal data array is\n") ;
    for(i=1;i<=10;i++)                        /*显示原序列之中的元素*/
        printf("%d ",k[i]);
    heapsort(k,10);                         	/*堆排序*/
    printf("\nThe result of quick sorting for the array is\n");
    for(i=1;i<=10;i++)                       	/*显示排序后的结果*/
        printf("%d ",k[i]);
    getche();
}

执行结果：