算法学习（五）——快速排序

淡淡的烟草味﹌ 2022-07-12 06:46 177阅读 0赞

# 算法学习（五）——快速排序 #

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 1]进行，以此达到整个数据变成有序[序列][Link 2]。（摘自百度百科）

首先快速排序的性能很好，但是快速排序是不稳定的。

问题：给定数组，进行排序。

方法：以数组的第一个元素作为特殊元素，每一次的目的是把数组中大于特殊元素的放在右边，小于特殊元素的放在左边，然后分别对左右两边的数组进行递归操作。

实现：

package com.xueyou;
    
    /**
     * Created by Administrator on 2017/2/14.
     */
    public class QuickSort {
        /**
         * 打印数组
         *
         * @param a
         */
        static void printArray(int[] a) {
            for (int num : a) {
                System.out.print(num + "\t");
            }
            System.out.println("");
        }
    
        static void quickSort(int[] a, int low, int high) {
            int i = low;
            int j = high;
            int k = a[i];
            while (i < j) {
                //把小于关键数据的放在左边
                while (i < j && a[j] >= k) {
                    j--;
                }
                if (i < j) {
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                    printArray(a);
                }
                //把大于关键数据的放在右边
                while (i < j && a[i] <= k) {
                    i++;
                }
                if (i < j) {
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                    printArray(a);
                }
            }
            if (low < i - 1) {
                quickSort(a, low, i - 1);
            }
            if (high > i + 1) {
                quickSort(a, i + 1, high);
            }
        }
    
        public static void main(String[] args) {
            int[] a = {6, 3, 1, 7, 9, 4, 6, 2};
            printArray(a);
            System.out.println("============排序中================");
            quickSort(a, 0, a.length - 1);
            System.out.println("============排序中================");
            printArray(a);
        }
    }

运行结果：

![Center][]

具体的排序过程如下：

![Center 1][]

[Link 1]: http://baike.baidu.com/view/96473.htm
[Link 2]: http://baike.baidu.com/subview/71968/12546268.htm
[Center]: /images/20220711/1ba4fb7350ed41e88c55f7d96ed936c7.png
[Center 1]: /images/20220711/2ce77a8ba9b946d28b0a62a6b4728537.png