面试题：手写一个快速排序

╰+哭是因爲堅強的太久メ 2023-07-16 03:45 68阅读 0赞

### 手写一个快速排序算法 ###

实现对数组  int\[\] arr = \{49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22\};进行排序

基本思想是：

*  1．先从数列中取出一个数作为基准数。
 *  2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 *  3．再对左右区间重复第二步，直到各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法。

动画：

![在这里插入图片描述][2019060415201822.gif]

代码如下：

package com.xzq.algorithm;
    
    
    /**
     * @ClassName: QuickSort
     * @description: 快速排序
     * @author: XZQ
     * @create: 2020/2/21 20:16
     **/
    public class QuickSort {
    
        public static void main(String[] args) {
            int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
            quickSort(arr, 0, arr.length - 1);
            System.out.println("排序后:");
            for (int i : arr) {
                System.out.println(i);
            }
        }
    
        private static int getIndex(int[] array, int low, int high) {
            int temp = array[low];
            while (low < high) {
                while (low < high && array[high] >= temp) {
                    high--;
                }
                array[low] = array[high];
                while (low < high && array[low] <= temp) {
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = temp;
            return low;
        }
    
        private static void quickSort(int[] array, int low, int high) {
            if (low < high) {
                int index = getIndex(array, low, high);
                quickSort(array, 0, index - 1);
                quickSort(array, index + 1, high);
            }
        }
    
    }

原理：

①先从队尾开始向前扫描且当low < high时,如果a\[high\] > tmp,则high–,但如果a\[high\] < tmp,则将high的值赋值给low,即arr\[low\] = a\[high\],同时要转换数组扫描的方式,即需要从队首开始向队尾进行扫描了  
②同理,当从队首开始向队尾进行扫描时,如果a\[low\] < tmp,则low++,但如果a\[low\] > tmp了,则就需要将low位置的值赋值给high位置,即arr\[low\]  = arr\[high\],同时将数组扫描方式换为由队尾向队首进行扫描.  
③不断重复①和②,知道low>=high时(其实是low=high),low或high的位置就是该基准数据在数组中的正确索引位置.

[2019060415201822.gif]: /images/20230528/e6a9a6200c5042fea5e592002224142f.png