Java数据结构（十）——冒泡排序、快速排序
文章目录
- 冒泡排序
- 算法介绍
- 代码实现
- 优化策略
- 复杂度和稳定性
- 快速排序
- 算法介绍
- 优化策略
- 非递归实现
- 代码演示
- 复杂度和稳定性
冒泡排序
算法介绍
冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就交换。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，就像冒泡一样。
冒泡排序算法的步骤如下（排升序）：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后每轮筛选出来的最大的值；
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
【图示】
代码实现
public void bubbleSort(int[] array) {
int len = array.length;
while(len > 0) {
len--;
for(int i = 0; i < len; i++) {
if(array[i] > array[i+1]) {
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
}
}
优化策略
上代码存在一个问题可以优化，这个问题是：当某次遍历交换完后序列有序，排序不会停止，而是继续走完所有的趟数。对此可以优化，使得在某趟遍历没有任何交换的情况下（已经有序），不再开始下一趟，直接跳出排序，代码如下：
public void bubbleSort() {
int len = array.length;
boolean flag = true;
while(len > 0 && flag) {
len--;
flag = false;
for(int i = 0; i < len; i++) {
if(array[i] > array[i+1]) {
flag = true;
int tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
}
}
}
}
优化代码中通过设置了一个boolean类型的变量，保证了当序列有序，能够及时结束排序。
复杂度和稳定性
时间复杂度：O(N^2)
优化后的冒泡排序在第一次遍历且没有交换发生时就会停止，因此某些时候时间复杂度可以从O(N^2)降低到O(N)。虽然优化后的冒泡排序在最好情况下有显著改进，但在最坏情况和平均情况下的时间复杂度并没有改变，仍为O(N^2)。
空间复杂度：O(1)
稳定性：稳定，通过控制交换的条件（相等时不交换）可以达到稳定。
快速排序
算法介绍
快速排序是一种高效的排序算法。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序使用 分治法策略 来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
（排升序）将序列划分为两个序列需要确定一个基准值，当划分结束后，基准值左边元素均小于该基准值，右边元素均大于该基准值。 实现这种划分有三种方式，分别是：挖坑法、Hoare法 和 前后指针法。
【挖坑法】
首先确定一个基准值，通常会选择序列最左边的元素，然后将基准值存放在key变量中（通常将存放基准值的变量命名为key），此时将基准值所在位置视为“坑”。需要其他元素来“填坑”，由于基准值是序列的最左边的元素，所以我们要从序列的最右端开始，向前寻找第一个比基准值小的元素作为填坑元素填到坑位，之后，坑位更新到填坑元素的位置，由于填坑元素是从右边开始寻找的，所以我们要从左边开始寻找第一个比基准值大的元素作为填坑元素填坑，更新坑位到填坑元素的位置，继续第二轮，接着上次右边的位置向左寻找第一个比基准值小的元素填坑……以此类推，当向右寻找和向左寻找的两个位置重合，结束循环，重合位置就是基准值应所在的位置，此时基准值左边的所有元素都小于基准值，基准值右边的所有元素都大于基准值，即确定了基准值的最终位置。
图示：
关键代码实现：
int key = array[0];//存放基准值
int pivot = 0;//坑位（下标值）
int left = 0;//左“指针”（下标值）
int right = array.length - 1;//右“指针”（下标值）
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
- 注意问题：
- 左右“指针”寻找填坑元素时，要注意判断
left < right，避免寻找过程中超出寻找范围 - 当 right 向前（left 向后）寻找比 key 值小（大）的元素时，对于遇到与 key 值相同值得处理，应该不是目标值，要跳过继续寻找。
- 左右“指针”寻找填坑元素时，要注意判断
【Hoare法】
首先选定一个基准值（通常最左边），创建两个“指针”，分别指向最左边和最右边，右指针从右向左移动时，它会寻找第一个小于基准值的元素；左指针开始从左向右移动，寻找第一个大于基准值的元素，找到后，进行交换；重复寻找并交换的过程，直到左右“指针”相遇；最后，将基准值与相遇的位置的元素交换。
关键代码实现：
int key = array[0];
int left = 0;
int right = array.length - 1;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
while(left < right && array[left] <= key) {
left++;
}
swap(array, left, right);
}
swap(array, 0, left);
- 注意问题：
- 先动右指针，再动左指针
- 指针寻找时找到与基准值一样的值，跳过继续寻找，即取等号
【前后指针法】
选定最左边元素为基准值，创建两个指针，这里命名为prev和cur，初始分别指向基准值位置和基准值下一个位置，cur负责向后寻找比基准值小的元素，找到了就让prev++然后交换两个指针指向的位置的元素，然后继续寻找交换，直到cur指针越界，最后，将prev指向的位置的元素与基准值元素交换。
关键代码实现：
int key = array[0];
int cur = 1;
int prev = 0;
while(cur < array.length) {
if(array[cur] < key && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
swap(array, 0, prev);
演示三种划分方法使用的元素序列是一致的，但最终划分的结果可能不同：
- 挖坑法：[15, 29, 29, 34, 87, 45, 63, 56, 78, 71]
- Hoare法：[29, 15, 29, 34, 87, 45, 63, 56, 78, 71]
- 前后指针法：[15, 29, 29, 34, 87, 45, 63, 56, 78, 71]
但即使划分的结果不同，最终都能满足基准值的位置是正确的，且其左边元素均比它小，右边的元素均比它大
三种划分方式的使用频率和重要程度即介绍的顺序：挖坑法 > Hoare法 > 前后指针法。
例如，有些快速排序的选择题会考察第n趟的结果，题目一般都是以挖坑法划分方式的，但如果利用挖坑法得到的结果不在选项中，则依次按照Hoare法和前后指针法尝试。
了解了划分方法后实际上只解决了快速排序的一步，每次经过划分后，都会有一个元素的最终位置确定，并且将序列被分为两个子序列，快速排序要做的是继续对左右子序列进行相同的划分，直到序列有序。可以以递归的方式实现：
【图示】
以挖坑法演示：
完整实现：
public void quickSort(int[] array, int begin, int end) {
if(begin >= end) {
return;
}
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
//递归地划分
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
我们假设每次划分后确定的基准值元素的最终位置都在序列的中间位置，于是通过下面的简单图可以理解快速排序的时间复杂度：
快速排序的平均时间复杂度是O(N*log2N)，但这建立在 每次划分后确定的基准值元素的最终位置都在序列的中间位置 的前提下，如果出现极端情况：每次每次划分后确定的基准值元素的最终位置都在序列的两侧（即序列有序），此时就会出现快速排序的最坏时间复杂度：O(N^2)的情况。
优化策略
【三数取中】
当序列有序时，快速排序的时间复杂度会达到O(N^2)级别，这是因为有序序列每次拿到的基准值都是序列的最值元素（最大值或最小值），这时候指针就得遍历整个序列。
为此，可以通过三数取中的方式来避免每次确定基准值时选到最值元素，三数取中的原理是：取出序列中位置最左、最右和中间的三个元素，比较它们的大小，选出第二大（即中间大）的元素，然后将它换到基准值位置（通常是最左边），这样取基准值时，就不会出现选到最值的极端情况了
以下是三数取中以及三数取中优化后的快速排序：
private void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
//三数取中
private int getMidIndex(int[] array, int left, int right) {
int mid = left + (right - left >> 1);
if(array[left] > array[right]) {
if(array[left] > array[mid]) {
return array[mid] > array[right] ? mid : right;
}else {
return left;
}
}else {
if(array[right] > array[mid]) {
return array[mid] > array[left] ? mid : left;
}else {
return right;
}
}
}
//三数取中后的快速排序
public void quickSort(int[] array, int begin, int end) {
if(begin >= end) {
return;
}
//取得中间大的元素的下标
int midIndex = getMidIndex(array, begin, end);
//交换，避免出现极端情况
swap(array, begin, midIndex);
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
//递归地划分
quickSort(begin, pivot - 1);
quickSort(pivot + 1, end);
}
【小区间优化】
对快速排序进行了三数取中优化后，实际上还能继续优化。
小区间优化是针对当待排序的数组的数据量较少时，采用其他排序方法（通常是直接插入排序）对小数组排序。因为对大量小数组进行递归调用和分区操作会产生较大的开销。
小区间优化需要确定一个阈值，这个阈值决定了小数组的长度到达多少时进行直接插入排序，阈值的确定与数据量有很大的关系，不过常见的阈值有8，10，15
小区间优化后的快速排序（采用10为阈值，仅作为代码演示）：
private void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
private int getMidIndex(int left, int right) {
int mid = left + (right - left >> 1);
if(array[left] > array[right]) {
if(array[left] > array[mid]) {
return array[mid] > array[right] ? mid : right;
}else {
return left;
}
}else {
if(array[right] > array[mid]) {
return array[mid] > array[left] ? mid : left;
}else {
return right;
}
}
}
//小区间优化的直接插入排序代码
public void insertSort(int[] array, int begin, int end) {
for(int i = begin + 1; i <= end; i++) {
int tmp = array[i];
int pos = i - 1;
for(int j = i - 1; j >= begin; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
pos--;
}else {
break;
}
}
array[pos+1] = tmp;
}
}
public void quickSort(int begin, int end) {
if(begin >= end) {
return;
}
int midIndex = getMidIndex(begin, end);
swap(array, begin, midIndex);
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
//小区间优化
if(pivot - 1 - begin <= 10) {
insertSort(array, begin, pivot - 1);
}else {
quickSort(begin, pivot - 1);
}
if(end - pivot - 1 <= 10) {
insertSort(array, pivot + 1, end);
}else {
quickSort(pivot + 1, end);
}
}
非递归实现
非递归实现需要用到栈，栈用来存储序列的左右边界下标，需要注意的是：
- 基于栈的“先入后出”特性，为了能先划分左子序列，我们必须先将右子序列的两个边界下标入栈，再将左子序列的两个边界下标入栈，以确保出栈时先拿到的是左子序列的边界下标
- 向栈中存放某个序列的两个边界下标时，也要注意栈的特性，比如，接下来的示例代码中，我们选择先将右边界下标入栈，再将左边界下标入栈
public void quickSortNoR(int[] array) {
//创建一个栈，并初始化栈的元素
Stack<Integer> stack = new Stack<>();
stack.push(array.length - 1);
stack.push(0);
//快速排序的核心代码
while(!stack.isEmpty()) {
//出栈，注意出栈元素的含义，要结合入栈顺序
int begin = stack.pop();
int end = stack.pop();
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
//入栈，入栈规则：先入右子序列的两个边界，再入左子序列的两个边界
if(end - pivot - 1 > 1) {
stack.push(end);
stack.push(pivot + 1);
}
if(pivot - 1 - begin > 1) {
stack.push(pivot - 1);
stack.push(begin);
}
}
}
演示代码并没有采用三数取中和小区间优化，读者可以自行尝试，也比较简单，理解了非递归代码后在合适的位置插入优化代码即可。
代码演示
方便起见，将代码再次展示：
递归实现（三数取中和小区间优化）：
public void quickSort(int begin, int end) {
if(begin >= end) {
return;
}
int midIndex = getMidIndex(begin, end);
swap(array, begin, midIndex);
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
//小区间优化
if(pivot - 1 - begin <= 10) {
insertSort(array, begin, pivot - 1);
}else {
quickSort(begin, pivot - 1);
}
if(end - pivot - 1 <= 10) {
insertSort(array, pivot + 1, end);
}else {
quickSort(pivot + 1, end);
}
}
private void swap(int[] array, int a, int b) {
int tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
private int getMidIndex(int left, int right) {
int mid = left + (right - left >> 1);
if(array[left] > array[right]) {
if(array[left] > array[mid]) {
return array[mid] > array[right] ? mid : right;
}else {
return left;
}
}else {
if(array[right] > array[mid]) {
return array[mid] > array[left] ? mid : left;
}else {
return right;
}
}
}
//小区间优化的直接插入排序代码
public void insertSort(int[] array, int begin, int end) {
for(int i = begin + 1; i <= end; i++) {
int tmp = array[i];
int pos = i - 1;
for(int j = i - 1; j >= begin; j--) {
if(array[j] > tmp) {
array[j+1] = array[j];
pos--;
}else {
break;
}
}
array[pos+1] = tmp;
}
}
非递归实现：
public void quickSortNoR(int[] array) {
Stack<Integer> stack = new Stack<>();
stack.push(array.length - 1);
stack.push(0);
while(!stack.isEmpty()) {
int begin = stack.pop();
int end = stack.pop();
int key = array[begin];
int left = begin;
int right = end;
int pivot = begin;
while(left < right) {
while(left < right && array[right] >= key) {
right--;
}
array[pivot] = array[right];
pivot = right;
while(left < right && array[left] <= key) {
left++;
}
array[pivot] = array[left];
pivot = left;
}
array[pivot] = key;
if(end - pivot - 1 > 1) {
stack.push(end);
stack.push(pivot + 1);
}
if(pivot - 1 - begin > 1) {
stack.push(pivot - 1);
stack.push(begin);
}
}
}
复杂度和稳定性
时间复杂度：O(N*log2N)
尽管快速排序的最坏时间复杂度为：O(N^2)，但快速排序的时间复杂度为O(N*log2N)是约定俗成的，我们可以通过例如三数取中来避免最坏情况的发生。
空间复杂度：O(log2N)~O(N)
O(log2N)主要是递归调用栈所占据的空间。在平均情况下，递归深度接近O(log2N)O(N)：最坏空间复杂度，当数组已经接近有序或完全逆序时，递归深度达到n，因此递归调用栈占据的空间也达到n。
稳定性：不稳定
完