流年似水博客开通了,本站主要是写关于Web和大数据方面内容,正在更新中,欢迎大家光临!
  1. 文章:97 篇
  2. 总浏览:54,851 次
  3. 评论:22条
  4. 最后更新:2020-06-08
  5. 分类目录:39 个

Java之快速排序详解

Java l, xy 520℃ 0评论

Java之快速排序详解

一、 快速排序介绍

    快速排序(Quicksort)是对冒泡排序的一种改进,具有速度快,对空间要求小等特点,是目前主要的排序方法。

 

二、 快速排序思想介绍

    2.1 基本思想  

    基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分

别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    2.2 基本步骤

        1. 首选选中待排序元素(一般为数组)的中间【(mid = left + right) / 2】 元素为一个基准数(pivot),将数组分为左边(下标: 0 至 mid - 1 )和右边(下标:mid + 1 至 right )

        2. 左边从头向后查找比基准数(pivot)的元素,并记录下标为l。右边从后向前查找比基准数(pivot)的元素,并记录下标为r。 交换两个下标位置的元素。

        3. 循环步骤2,一直到左边下标l大于等于右边下标r为止。此为一次完成排序过程。经过此步骤,可以得到左边(下标:left 至 l )一定小于等于基准数(pivot),右边(r 至 right)一定大于等于基准数(pivot)

        4. 对左边(下标:left 至 l )递归执行步骤1-3, 对右边(r 至 right)递归执行步骤1-3,从而对两边进行排序。最终整个待排序元素(一个为数组)排成有序。

三、 快速排序过程动画图(本图是将left作为基准值)

四、 快速排序时间复杂度、空间复杂度、稳定性

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(nlog₂n) O(nlog₂n) O(n²) O(1)(原地分区递归版)

快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.

Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.

五、 快速排序Java实现(递归实现)


import java.util.Arrays;

public class QuickSort {


public static void main(String[] args) {
int[] arr = new int[]{29, 88, 33, 20, 57, 76};
quickSort(arr, 0, arr.length - 1);
Arrays.stream(arr).forEach(System.out::println);
}

/**
* 快速排序
* @param arr 待排序数组
* @param left 数组首个元素下标,通常为0
* @param right 数组尾部元素下标,通常为arr.length() - 1
*/
/**
* @param arr
*/
public static void quickSort(int[] arr, int left, int right) {

int mid = (left + right) / 2;
int pivot = arr[mid];
int l = left;
int r = right;

while (l < r) {
// 找到左边第一个大于pivot元素的下标
while (arr[l] < pivot) {
l++;
}
// 找到右边第一个小于pivot元素的下标
while (arr[r] > pivot) {
r--;
}

// 左边下标大于等于右边下标,不用做交换,直接退出循环
if (l >= r) {
break;
}

// 交换两者的位置
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;


// 左边找到了pivot或者左边找到了与pivot相等的值,交换以后,右边可以-1,减少查找次数
if (arr[l] == pivot) {
r--;
}
// 右边找到了pivot或者右边找到了与pivot相等的值,交换以后,左边可以-1,减少查找次数
if (arr[r] == pivot) {
l++;
}

}
// 左边下标和右边下标重合
if (l == r) {
// 左边+1
l++;
// 右边-1
r--;
}

// 左边递归
if (left < r) {
quickSort(arr, left, r);
}
// 右边递归
if (right > l) {
quickSort(arr, l, right);
}
}
}

六、 理解快速排序可能出现的问题

        1. 这里的基准数(pivot)可以使用mid,也可以使用left或者right

        2. 使用mid作为基准值(pivot)时,基准值(povit)的位置可能出现改变

转载请注明:流年似水 » Java之快速排序详解

喜欢 (2)or分享 (0)

Warning: copy(https://cn.gravatar.com/avatar/?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239

Warning: copy(/wp-content/themes/yusi1.0/img/default.png): failed to open stream: No such file or directory in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 243
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址