【排序算法】之快排

本文主要是介绍【排序算法】之快排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快排注意点：

1. 明确快排终止条件：left >= right，即只有一个元素或者没有元素。
2. 明确指针移动条件:start < end，即首指针在尾指针右边时才能移动。
3. 明确指针定义：定义指针时，两个指针一定要把基准元素包含进去。（因为指针相交时交换元素并没有判断与基准元素的大小，特殊情况下：一个指针没动，另一个指针直接移动到头，此时指针的终止条件也可能是因为指针相交了，元素与基准元素的大小比较未知，这时候与基准元素交换可能是一次错误的交换，但是如果把基准元素包含进来，就会与基准元素自身交换，不会产生影响）
4. 明确指针移动顺序：当选取最左边的元素为基准元素时，先移动的指针一定要是右边的指针；当选取最右边的元素为基准元素时，先移动的指针一定要是左边的指针。

注意：！！！！

当选取最左边的元素为基准元素时，先移动的指针一定要是右边的指针。
当选取最右边的元素为基准元素时，先移动的指针一定要是左边的指针。

public class FastSort {public static void quikSort(int[] arr, int left, int right) {// 1.快排终止条件（递归出口）：只有一个元素或者无元素，不进行快排if (left >= right) {return;}// 2.选取的基准元素：以数组左边的元素为基准元素int num = arr[left];// 定义首尾指针int start = left;int end = right;// 3.指针移动条件：指针未相交while (start < end) {// 先移动右边的指针（因为选取的是最左边的元素作为基准元素）while (start < end && arr[end] >= num) {end--;}// 再移动左边的指针while (start < end && arr[start] <= num) {start++;}// 两指针终止但没相交，交换元素if (start < end) {int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}}// 4.两指针相交，排序结束，将基准元素放入指针相交位置arr[left] = arr[start];arr[start] = num;// 5.继续递归：分别对基准元素左右两边的元素进行快排//快排左边quikSort(arr, left, start - 1);//快排右边quikSort(arr, start + 1, right);}//主函数public static void main(String[] args) {int[] arr = {34, 1, 5, -2, 0, 35, 36, 38};quikSort(arr, 0, arr.length - 1);for (int value : arr) {System.out.print(value+" ");}}
}

这篇关于【排序算法】之快排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---