快速排序算法
试题类型:编程题    难度:中等

对下面的一组数按小到大进行排序,使用快速排序算法。

89,23,69,101,12,90,36,19


全部题解
快速排序算法
编程训练营官方题解

快速排序是冒泡排序的改进,排序完成也是经过一趟或多趟排序。一趟快速排序采用从两头向中间扫描的方法,同时交换与基准值逆序的元素。

该算法的实现可分为以下几步:

(1)在待排序的N个元素中任取一个元素(通常取第一个元素)作为基准,称为基准值;

(2)定义两个索引 left 和 right 分别表示数组的头索引和尾索引,设置变量temp存储基准值;

(3)尾索引向前扫描,直至找到比基准值小的元素(left!= right),并替换首索引对应的值;

(4)首索引向后扫描,直到找到比基准值大于的元素(left!=right),并替换尾索引对应的值;

(5)若在扫描过程中首索引等于尾索引(left ==right),则一趟排序结束,将基准值替换首索引所对应的值;

(6)一趟排序结束后,待排序数组被分为两个分区,左侧分区为[0,left-1],右侧分区为[right+1,end],其中end为数组的结束索引。

(7)对每一个部分重复步骤1至6,直到分区中只有一个元素时,排序完成。

例如要排序的一组数为:

18,9,22,31,12,17

将这组数从小到排序,排序过程为:

(1)初始状态,数组名称为A,i、j为数组索引,分别赋值为0和5,选择A[1]为基准数,A[1]赋值给temp变量,temp变量的值为基准数。

11.png

(2)移动j索引(从右往左顺序移动),在移动过程中,若A[j]大于等于基准数,继续右移j;若A[j]小于等于基准数,将A[j]赋值给A[i]。

12.png

(3)移动i索引(从左往右顺序移动),在移动过程中,若A[i]小于等于基准数,继续右移i;若A[i]大于基准数,将A[i]赋值给A[j]。

13.png

(4)继续移动j索引(从右往左顺序移动),在移动过程中,若A[j]大于等于基准数,继续右移j;若A[j]小于等于基准数,将A[j]赋值给A[i]。

14.png

(5)移动i索引(从左往右顺序移动),在移动过程中,若A[i]小于等于基准数,继续右移i;若A[i]大于基准数,将A[i]赋值给A[j];若i与j相等,结束该趟排序,temp赋值给A[i]。

15.png

此时,一趟排序完成。待排序数组被分为两个分区[0,i-1]和[j+1,5],对这两个分区进行下一趟排序,直到分区只有一个元素时,排序完成。


Java代码:

public class QuartSort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        // TODO Auto-generated method stub
           int[] arr = {18, 9, 22, 31, 12, 17};
 
            quickSort(arr, 0, arr.length - 1);
 
            for (int i : arr) {
                System.out.print(i + "\t");
            }
    }
 
     /**
     * @param arr  待排序数组
     * @param left 待排序数组头索引
     * @param right 待排序数组尾索引
     */
    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
 
        int i = left;
        int j = right;
        //待排序的第一个元素作为基准值
        int temp = arr[i];
 
        //从左右两边交替扫描,直到i == j
        while (i < j) {
            while (j > i && arr[j] >= temp) {
                //从右往左扫描,找到第一个比基准值小的元素
                j--;
            }
 
            //arr[j]赋值给arr[i]
            arr[i] = arr[j];
 
            while (i < j && arr[i] <= temp) {
                //从左往右扫描,找到第一个比基准值大的元素
                i++;
            }
 
            //arr[i]赋值给arr[j]
            arr[j] = arr[i];
        }
        // 基准值归位
        arr[i] = temp;
        //对基准值左边的元素进行递归排序
        quickSort(arr, left, i-1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, j+1, right);
    }
   
}


  • 备案号:鲁ICP备15001146号
  • @1997-2018 潍坊米粒花网络技术有限公司版权所有