首页 > 编程语言 > 详细

快速排序算法

时间:2015-11-25 16:52:33      阅读:294      评论:0      收藏:0      [点我收藏+]

排序算法的思想呢,我看了许多,觉得比较生动的是:挖坑填坑再分治

  1. 把第一个数作为基准数挖出来,哨兵j从右往左找出比它小或者等于的数,把它挖出来,填进刚刚的坑里
  2. 填了一个坑,也新挖了一个坑,哨兵i从左往右,找出比基准数大的数,又挖出来,填入新的坑里
  3. 然后又是j继续从右往左……直到i和j相遇
  4. 相遇了,就把基准数填到最后一个坑里,也就是i和j相遇的位置
  5. 接下来分治,就是相遇点左边、右边分别快排
void QuickSort(int DataArray[],int left,int right)
{
    if(left>=right)return;

    int key,i,j;

    i=left;
    j=right;
    key=DataArray[i];
    while(i<j)
    {
        while(DataArray[j]>key&&j>i)j--;
        if(j>i)
        {
            DataArray[i]=DataArray[j];
            i++;
        }
        while(DataArray[i]<=key&&i<j)i++;
        if(j>i)
        {
            DataArray[j]=DataArray[i];
            j--;
        }
    }
    DataArray[i]=key;
    QuickSort(DataArray,left,i-1);
    QuickSort(DataArray,i+1,right);
}

调用:

    QuickSort(a,0,n-1);          //数组a[],长度为n

 

快速排序算法

原文:http://www.cnblogs.com/flipped/p/4995054.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!