文
章
目
录
章
目
录
本文重点讲解Java实现快速排序经典代码和算法思路。
快速排序的基本思想
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一 部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序 过程可以递归进行，以此达到整个数据变成有序序列。
算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”(pivot);
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
切分原理
把一个数组切分成两个子数组的基本思想：
- 1.找一个基准值，用两个指针分别指向数组的头部和尾部；
- 2.先从尾部向头部开始搜索一个比基准值小或等于的元素，搜索到即停止，并记录指针的位置；
- 3.再从头部向尾部开始搜索一个比基准值大或等于的元素，搜索到即停止，并记录指针的位置；
- 4.交换当前左边指针位置和右边指针位置的元素；
- 5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
快速排序图解
快速排序Java代码实现
/**
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + "\t");
}
}
/**
* @param arr 待排序列
* @param leftIndex 待排序列起始位置
* @param rightIndex 待排序列结束位置
*/
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
}
int left = leftIndex;
int right = rightIndex;
//待排序的第一个元素作为基准值
int key = arr[left];
//从左右两边交替扫描，直到left = right
while (left < right) {
while (right > left && arr[right] >= key) {
//从右往左扫描，找到第一个比基准值小的元素
right--;
}
//找到这种元素将arr[right]放入arr[left]中
arr[left] = arr[right];
while (left < right && arr[left] <= key) {
//从左往右扫描，找到第一个比基准值大的元素
left++;
}
//找到这种元素将arr[left]放入arr[right]中
arr[right] = arr[left];
}
//基准值归位
arr[left] = key;
//对基准值左边的元素进行递归排序
quickSort(arr, leftIndex, left - 1);
//对基准值右边的元素进行递归排序。
quickSort(arr, right + 1, rightIndex);
}
}
快速排序的另一种实现，似乎更容易理解：
public static void QuickSort(int []arr,int low,int high) {
if(low<high) {
int pivotpos=partition(arr,low,high);
QuickSort(arr,low,pivotpos-1);
QuickSort(arr,pivotpos+1,high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot=arr[low];
while(low<high) {
//起初，一定要从右边指针开始，因为arr[low]的值已经扔给了pivot，arr[low]
//想象成无数字的空位
while(low<high&&pivot<=arr[high]) {
--high;
}
//把比pivot的小的数扔到左边指针
//把arr[high]扔到arr[low]这个空位上
//然后，high位置可以想象成无数字的空位
arr[low]=arr[high];
while(low<high&&arr[low]<=pivot) {
++low;
}
//把比pivot大的数扔到右边
//把arr[low]扔到arr[high]这个空位上
//然后，low位置可以想象成是无数字的空位
arr[high]=arr[low];
}
//此时low==high,return high也一样
arr[low]=pivot;
return low;
}
}
总结
以上就是Java实现快速排序经典代码和算法思路的全部内容了，希望对你有帮助！
