排序算法第二谈：快速排序

忘是亡心i 2023-01-01 12:56 129阅读 0赞

## 思路 ##

把一个数组切分成两个子数组的基本思想：

1.  找一个基准值，用两个指针分别指向数组的头部和尾部；
2.  先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置
3.  再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.  交换当前左边指针位置和右边指针位置的元素；
5.  重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

![image][]

public static void quickSort(int[] arr, int left, int right) { 
            if (left >= right) { 
                return;
            }
            int fun = fun(arr, left, right);
            quickSort(arr, left, fun - 1);
            quickSort(arr, fun + 1, right);
        }
    
        /** * 对数组，从索引lo到索引hi之间的元素进行分组并返回分组界限对应的索引 * * @param arr * @param left * @param right */
        public static int fun(int[] arr, int left, int right) { 
            int l = left + 1;//左边索引
            int r = right;//右边索引
            int key = arr[left];//取最左边一个数为基值
            while (true) { 
                while (l < r) { //从左往右遍历，找到比基值大的数
                    if (arr[l] > key) break;
                    l++;
                }
                while (l <= r) { //从右往左遍历
                    if (arr[r] < key) break;
                    r--;
                }
                //交换
                if (l >= r) break;
                else exchage(arr, l, r);
            }
            //把左边第一个元素和r索引交换
            exchage(arr, left, r);
            return r;
        }
    
        /** * 交换元素 * * @param arr * @param i * @param j */
        public static void exchage(int[] arr, int i, int j) { 
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

**速度**

![image.png][]

[image]: /images/20221120/128e8cd01bae491f9805e67b604e812e.png
[image.png]: /images/20221120/fe8e579138b04b0c866c90f0361e18f3.png