快速排序算法思想
快速排序和归并排序是互补的，归并排序将整个数组分成小数组，然后将排好序的小数组归并以将整个数组排序；而快速排序是在将大数组分成小数组的时候排序，当小数组小到不可再分的时候，排序也就完成了。
1.首先选择一个中间元素（一般选左端或者右端）。
2.分别获取除中间元素外的左右两端的索引。
3.由左右两端逐渐向中间迭代，每迭代一步比较一下索引中的元素和中间元素，当左边出现比中间元素大的元素的时候，暂停左边的迭代，当右边迭代出比中间元素小的元素的时候，右边迭代也暂停，交换左右两边的元素。
4.重复步骤3，直到左右两边的索引相遇，然后将中间元素移动到中间，这时中间元素左边的元素都比它小，右边的元素都比它大。
5.将上面的中间元素左右两边当成两个数组，分别进行上述过程。
6.重复以上步骤直到数组不可再分。
快速排序算法实现
public static void main(String[] args) {
int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
int low = 0;
int high = arr.length - 1;
quickSort(arr, low, high);
for (int i : arr) {
System.out.print(i + " ");
}
}
/**
* 快速排序
* @param arr
* @param low
* @param high
*/
private static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
// 分成两个
int p1 = getPartion(arr, low, high);
int p = getPartionOne(arr, low, high);
System.out.println(p1 == p);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
/**
* 切分
* @param arr
* @param left
* @param right
* @return
*/
private static int getPartionOne(int[] arr, int left, int right) {
int tmp = arr[left];
int i = left;
int j = right + 1;
while (true) {
while (arr[++i] < tmp) {
}
while (arr[--j] > tmp) {
}
if (i >= j) {
break;
}
exchage(arr, i, j);
}
exchage(arr, left, j);
return left;
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private static void exchage(int[] arr, int i, int j) {
int aux = arr[i];
arr[i] = arr[j];
arr[j] = aux;
}
/**
* 总感觉这个切分更好理解
* @param arr
* @param left
* @param right
* @return
*/
private static int getPartion(int[] arr, int left, int right) {
int tmp = arr[left];
while (left < right) {
while (left < right && arr[right] > tmp)
right--;
arr[left] = arr[right];
while (left < right && arr[left] <= tmp)
left++;
arr[right] = arr[left];
}
arr[left] = tmp;
return left;
}
算法复杂度
1.平均时间复杂度： O(NLogN)
2.最好情况时间复杂度： O(NLogN)
3.最差情况时间复杂度： O(NLogN)
4.所需要额外空间： O(1)
算法稳定性
- 快速排序是不稳定的
想看完整版请点击：快速排序
