快速排序(Quick Sort)-蒲公英云

快速排序(Quick Sort)

Dear 丶 2022-07-13 11:08 247阅读 0赞

一、算法原理

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数据放到它前面，所有比它大的数据放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法,也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

二、一般快速排序算法的步骤

设置两个变量i、j,排序开始的时候:i=0;j=N-1;
以第一个数组元素作为关键数据,赋值给key,即key=A[0];
从j开始向前搜索,即由后开始向前搜索(j- -),找到第一个小于key的值A[j],将A[i]和A[j]互换;
从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的值A[i],将A[i]和A[j]互换;
重复第3、4步,直到i=j;

三、快速排序算法的具体流程

①首先设置两个变量i和j,分别指向序列的首尾元素
  ②该示例是以第一个元素为基准,从小到大进行排列。让j从后向前进行查询,直到找到第一个小于66的元素。
  则将最后一个j指向的数23,和i指向的66交换位置。然后将i从前向后查询，直到找到第一个大于66的元素76。

将76和66位置互换。让j从后向前进行查询,直到找到第一个小于66的元素57

将57和66交换位置

然后将i从前向后查询,直到找到一个大于66的元素81。

将81和66交换位置
  让j从后向前查询,直到找到第一个小于66的元素26。

让26和66交换位置
  此时i,j都同时指向目标元素66
  查找停止
  所得到的序列就是第一趟排序的序列

第一趟排序结束,66左边的数都比66小,66右边的数都比66大
  再对66左边的序列和右边的序列分别递归调用上述过程

四、代码实现(Java)

public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{57, 68, 59, 52, 72, 28, 96, 33, 24, 19};
        quickSort(array, 0, array.length-1);
        for(Integer i : array){
            System.out.print(i + " ");
        }
    }
    public static void quickSort(int[] numbers, int start, int end) {   
        if (start < end) {   
            int base = numbers[start]; // 选定的基准值（第一个数值作为基准值）   
            int temp; // 记录临时中间值   
            int i = start, j = end;   
            do {   
                while ((numbers[i] < base) && (i < end))   
                    i++;   
                while ((numbers[j] > base) && (j > start))   
                    j--;   
                if (i <= j) {   
                    temp = numbers[i];   
                    numbers[i] = numbers[j];   
                    numbers[j] = temp;   
                    i++;   
                    j--;   
                }   
            } while (i <= j);   
            if (start < j){   
                quickSort(numbers, start, j);
            }   
            if (end > i){   
                quickSort(numbers, i, end);
            }   
        }   
    }
}