关于快速排序 - 黑马程序员技术交流社区

每趟取一个参照记录，称为枢轴（或支点），先从右向左，逐个记录与枢轴比较，如果逆序则交换，再从左向右，逐个记录与枢轴比较，如果逆序则交换，反复进行，直到左右相遇，结束一趟排序，并将枢轴记录交换到最终所在的位置上。所有大于枢轴的记录记录在右边，小于的在左边，一趟快速排序过程称为一个划分。然后分别对左右两部分进行相同的划分（或分割），得到4部分，再对每部分做相同划分，依次继续下去，直到每个小部分只有一个记录，排序结束。显然，对部分的划分操作完全相同，只是范围需修改，因此可以用递归实现，且最多经过[log 2 （n +1）趟划分，排序结束。

package com.itheima.util;
/**
* 排序工具类
*
* @author mrng
*
*/
public class SortUtils {
/**
* 快速排序如果调用此方法，次方法会再掉用quickSort(String[] strArr, int left, int rigth)方法
* left默认为0， right默认为strArr.length-1
*
* @param strArr
*/
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
/**
* 快速排序此方法可以对数组需要排序的区间进行定制
*
* @param strArr
* @param left
* @param right
*/
public static void quickSort(int[] arr, int left, int right) {
// 数组中间的元素
int middle = arr[(left + right) / 2];
// 临时变量，用于交换数组元素使用
int temp;
// 向后搜索的指针
int i = left;
// 向前搜索的指针
int j = right;
do {
while (arr[i] < middle && i < right)
i++; // 找出左边比中间值大的数
while (arr[j] > middle && j > left)
j--; // 找出右边比中间值小的数
if (i <= j) { // 将左边大的数和右边小的数进行交换
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j); // 当两个指针交错时停止
// 将数组分开两半，确定每个数字的正确位置
if (i < right) {
quickSort(arr, i, right);
}
if (j > left) {
quickSort(arr, left, j);
}
}
/**
* 冒泡排序法
*
* @param arr
*/
public static void BubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
}
}
}
}
/**
* 选择排序法
*/
public void SelectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
}
}
}

复制代码