快速排序
2019-04-20 本文已影响0人
攻城狮l
一、快速排序算法
快速排序（Quicksort）是对冒泡排序的一种改进。
二、算法思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤如下：
1.找到数组中的一个数为基准（一般是数组中的第一个数），然后从右向左找到第一个比基准数小的数，交换位置
2.然后以当前位置，从左到右的找到第一个比基准数大的数，交换位置
3.重复步骤1和2，直到左右两个位置相等，然后把基准数存入当前位置，此时 基准数左边的数字 <=基准数 <=基准数右边的数字
4.然后以当前基准数位置为分界，分为左右两个数组，进行排序，循环执行步骤1,2和3。
5.如果可排序区间只有一个元素，则说明当前循环排序完成
三、代码实现
package xzg.algorithm;
/**
* 快速排序
*/
public class QuickSort {
public static void main(String[] args) {
// int[] heights = {181, 169, 187, 166,150,172, 163, 191, 189, 182};
int[] heights = {5, 7, 1, 6, 8, 6};
quickSortArr(heights, 0, heights.length - 1);
System.out.println("------排序完成-------");
// 输出排序后的结果
for (int height : heights) {
System.out.print(height + " ");
}
}
/**
* @param array 指定的数组
* @param start 需要快速排序的数组索引起点
* @param end 需要快速排序的数组索引终点
*/
public static void quickSort(int[] array, int start, int end) {
System.out.println("------排序前-------");
for (int height : array) {
System.out.print(height + " ");
}
System.out.println();
// i相当于助手1的位置，j相当于助手2的位置
int i = start, j = end;
// 取第1个元素为基准元素
int pivot = array[i];
// 表示空位的位置索引，默认为被取出的基准元素的位置
int emptyIndex = i;
// 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
while (i < j) {
// 助手2开始从右向左一个个地查找小于基准元素的元素
int jValue = array[j];
while (i < j && pivot <= jValue) {
j--;
}
if (i < j) {
// 如果助手2在遇到助手1之前就找到了对应的元素，就将该元素给助手1的"空位"，j成了空位
array[emptyIndex] = array[emptyIndex = j];
}
// 助手1开始从左向右一个个地查找大于基准元素的元素
int iValue = array[i];
while (i < j && iValue <= pivot) {
i++;
}
if (i < j) {
// 如果助手1在遇到助手2之前就找到了对应的元素，就将该元素给助手2的"空位"，i成了空位
array[emptyIndex] = array[emptyIndex = i];
}
for (int height : array) {
System.out.print(height + " ");
}
System.out.println();
}
// 助手1和助手2相遇后会停止循环，将最初取出的基准值给最后的空位
array[emptyIndex] = pivot;
System.out.println("------排序后-------");
for (int height : array) {
System.out.print(height + " ");
}
System.out.println();
// =====本轮快速排序完成=====
// 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
if (i - start > 1) {
quickSort(array, 0, i - 1);
}
// 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
if (end - j > 1) {
quickSort(array, j + 1, end);
}
}
/**
* 快速排序算法：<br/>
* 算法思想：<br/>
* 1.找到数组中的一个数为基准（一般是数组中的第一个数），然后从右向左找到第一个比基准数小的数，交换位置<br/>
* 2.然后以当前位置，从左到右的找到第一个比基准数大的数，交换位置<br/>
* 3.重复步骤1和2，直到左右两个位置相等，然后把基准数存入当前位置，此时 基准数左边的数字 <=基准数 <=基准数右边的数字<br/>
* 4.然后以当前基准数位置为分界，分为左右两个数组，进行排序，循环执行步骤1,2和3
* 5.如果可排序区间只有一个元素，则说明当前循环排序完成
*
* @param arr
* @param start
* @param end
*/
public static void quickSortArr(int[] arr, int start, int end) {
//数组左边位置，也是基准元素的初始化位置
int left = start;
//数组右边位置
int right = end;
//基准数
int temp = 0;
//当前排序区间只有一个元素
if (left < right) {
//以可排序区间的第一个数字为基准数据
temp = arr[left];
//当前排序区间元素大于1
while (left != right) {
while (left < right & temp <= arr[right]) {
//在当前排序区间中，从右向左找到第一个小于基准元素的数据所在的位置
right--;
}
//找到相关元素，把其赋值给原基准元素所在的位置
arr[left] = arr[right];
System.out.println("----------while---从右向左找到第一个小于基准元素---right=" + right+" left="+left);
for (int height : arr) {
System.out.print(height + " ");
}
System.out.println();
while (left < right && temp >= arr[left]) {
//在当前排序区间中，从左向右找到第一个大于基准元素的数据所在的位置
left++;
}
//找到相关元素，把其赋值给原基准元素所在的位置
arr[right] = arr[left];
System.out.println("----------while---从左向右找到第一个大于基准元素---right=" + right+" left="+left);
for (int height : arr) {
System.out.print(height + " ");
}
System.out.println();
}
//基准元素归位,此时left=right
arr[left] = temp;
System.out.println("------排序后--基准元素归位---right=" + right+" left="+left);
for (int height : arr) {
System.out.print(height + " ");
}
System.out.println();
//对基准元素右边的元素进递归排序
quickSortArr(arr, right + 1, end);
//对基准元素左边的元素进行递归排序
quickSortArr(arr, start, left - 1);
}
}
}
输出结果
----------while---从右向左找到第一个小于基准元素---right=2 left=0
1 7 1 6 8 6
----------while---从左向右找到第一个大于基准元素---right=2 left=1
1 7 7 6 8 6
----------while---从右向左找到第一个小于基准元素---right=1 left=1
1 7 7 6 8 6
----------while---从左向右找到第一个大于基准元素---right=1 left=1
1 7 7 6 8 6
------排序后--基准元素归位---right=1 left=1
1 5 7 6 8 6
----------while---从右向左找到第一个小于基准元素---right=5 left=2
1 5 6 6 8 6
----------while---从左向右找到第一个大于基准元素---right=5 left=4
1 5 6 6 8 8
----------while---从右向左找到第一个小于基准元素---right=4 left=4
1 5 6 6 8 8
----------while---从左向右找到第一个大于基准元素---right=4 left=4
1 5 6 6 8 8
------排序后--基准元素归位---right=4 left=4
1 5 6 6 7 8
----------while---从右向左找到第一个小于基准元素---right=2 left=2
1 5 6 6 7 8
----------while---从左向右找到第一个大于基准元素---right=2 left=2
1 5 6 6 7 8
------排序后--基准元素归位---right=2 left=2
1 5 6 6 7 8
------排序完成-------
1 5 6 6 7 8
Process finished with exit code 0
四、算法分析
空间复杂度为O(log2n)
参考资料
