快速排序（Java实现）

爱被打了一巴掌 2024-04-17 05:51 6阅读 0赞

import java.util.Arrays;
    
    public class Main {
    
        public static void main(String[] args) {
            int[] test1 = {1, 1, 1, 2, 3, 3, 3};
            quickSort(test1);
            for (int i = 0; i < test1.length; i++) {
                System.out.print(test1[i] + ",");
            }
    
            System.out.println("----------------------------");
    
            int[] test2 = {5, 1, 9, 3, 7, 4, 8, 6, 2};
            quickSort(test2);
            for (int i = 0; i < test2.length; i++) {
                System.out.print(test2[i] + ",");
            }
        }
    
        static void quickSort(int[] array) {
            quickSort(array, 0, array.length - 1);
        }
    
        /**
         * 对线性表的子序列[low,high]做快速排序
         *
         * @param array
         * @param low
         * @param high
         */
        static void quickSort(int[] array, int low, int high) {
            int baseIndex;
            if (low < high) {
                /*将array一分为二，算出基准数的数组下标，使得基准左边的数都比它大，基准右边的数都比它小。此时基准已经位于它在数组中的最终位置*/
                baseIndex = partition(array, low, high);
    
                quickSort(array, low, baseIndex - 1); /* 对低半部分做递归排序 */
                quickSort(array, baseIndex + 1, high); /* 对高半部分做递归排序 */
            }
    
        }
    
    
        /**
         * 出基准数的数组下标，使得基准左边的数都比它大，基准右边的数都比它小
         * @param array
         * @param low
         * @param high
         * @return
         */
        static int partition(int[] array, int low, int high) {
            int baseValue; /* 基准值 */
            baseValue = array[low]; /* 出于简单，选子表的第一个记录为基准 */
    
            while (low < high) { /* 从表的两端，交替向中间扫描 */
                while (low < high && array[high] >= baseValue) { /* 从后往前找，直到找到第一个小于基准的值 */
                    --high;
                }
                swap(array, low, high); /* 遇到array[high]<baseValue,将该array[high]交换到array[low] */
    
                while (low < high && array[low] <= baseValue) { /* 从前往后找，直到找到第一个大于基准的值 */
                    ++low;
                }
                swap(array, low, high); /* 遇到array[high]>baseValue,将该array[low]交换到array[high] */
            }
            //运行至此low==high==baseIndex
    
            return low; /* 返回baseValue这个值所在的数组下标 */
    
        }
    
        static void swap(int[] array, int i, int j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }

运行结果：

> 1,1,1,2,3,3,3,  
> \----------------------------  
> 1,2,3,4,5,6,7,8,9,