排序算法001-快速排序


首先我们要知道,快速排序是对冒泡排序的改进,通常情况下快速排序的速度最快,但是由于使用了递归,所以会占用大量内存。快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于二分的思想。(《啊哈C》)


算法思想从数组里挑选一个数,将其他大于这个数的数放在它的右边(假设从小到大排列),小于他的放在左边。这样的话数组被分成左右俩数组,然后重复对子数组进行上述操作。


快速排序步骤:

1)排序开始的时候:i=0(数组起始位置),j=N-1(数组结束位置);

2)以第一个数组元素作为关键数据,key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j -- ),找到第一个小于key的值A[j],A[i]与A[j]交换;

4)从i开始向后搜索,即由前开始向后搜索(i ++ ),找到第一个大于key的A[i],A[i]与A[j]交换;

5)重复第3、4、5步,直到 i=j;

6)对子数组重复上述步骤(递归)


C 具体实现

#include <stdio.h>
int a[101],n;//定义全局变量,这两个变量需要在子函数中使用

void quicksort(int left,int right)
{    
    int i,j,t,temp;
        
    if(left>right)       
        return;
      
    temp=a[left]; //temp中存的就是基准数
    i=left;
    j=right;    
    
    while(i!=j){                   
        //顺序很重要,要先从右边开始找
        while(a[j]>=temp && i<j)
            j--;                  
            
        //再找右边的
        while(a[i]<=temp && i<j)
            i++;                   
            
        //交换两个数在数组中的位置
        if(i<j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }    
    
    //最终将基准数归位
    a[left]=a[i];
    a[i]=temp;
   
    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程
    quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程
    
}

int main()
{    
    int i,j,t;    
    
    //读入数据
    scanf("%d",&n);    
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        
    quicksort(1,n); //快速排序调用 
      
    //输出排序后的结果
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
        
    getchar();getchar();    
    return 0;
}


运行结果

happysneaker.com


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论