教你学习快速排序算法-程序员必备哦

作者: TryEnough | 来源:发表于2019-03-01 17:31 被阅读8次

    支持原文:https://tryenough.com/arithmetic-quitsort

    举个例子

    排序这个序列:6 1 2 7 9 3 4 5 10 8

    • 步骤1:选择一个基准数作为对比的开始值,这里选择第一个数6:
    • 步骤2、先从右往左找一个小于 6 的数,再从左往右找一个大于 6 的数。
    • 步骤3、然后交换他们

    变成这样子:

    继续执行步骤2和3,直到两个哨兵相遇,:


    左右两个哨兵都走到3:


    • 步骤4:将开始选择基准数字6换到中间,测试6左边的数都小于6,右边的数都大于6。完成第一次循环:

    第一次完成之后,再按照此方法分别对6左右两边的数列进行递归排序即可。是不是很简单。

    看下代码就更清晰了:

    void quicksort(int a[], 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(a, left,i-1);//继续处理左边的,这里是一个递归的过程
            quicksort(a, i+1,right);//继续处理右边的 ,这里是一个递归的过程
        }
    

    也可以这么写:

    /**
         * 快排
         * @param arr
         * @param low
         * @param high
         * @return
         */
        public static int[] quit(int arr[], int low, int high) {
            int l = low;
            int h = high;
            int key = arr[l];  //先找出一个数作为基准数(这里取数组最中间的一位)
    
            while (l < h) {
                while (l < h && arr[h] >= key) h --; //从后向前:寻找比基准数小的数据,如果找到,停下来
                if (l < h) {  //“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找
                    arr[l] = arr[h];
                    l ++;
                }
                while (l < h && arr[l] <= key) l ++; //从前向后:寻找比基准数大的数据,如果找到,停下来
                if (l < h) { ////“探测”到了符合要求的数据,则交换数据,继续顺着方向寻找
                    arr[h] = arr[l];
                    h --;
                }
            }
            arr[l] = key;
            if (l > low) quit(arr, low, l - 1);
            if (h < high) quit(arr, h + 1, high);
            return arr;
        }
    

    支持原文:https://tryenough.com/arithmetic-quitsort

    相关文章

      网友评论

        本文标题:教你学习快速排序算法-程序员必备哦

        本文链接:https://www.haomeiwen.com/subject/rffjuqtx.html