Java快速排序 - Kirin博客

Java快速排序

作者: Bee

全网最全的网络资源分享网站

标签:

Java

特别声明:部分文章为网络转载,资源使用一般不提供任何帮助,特殊资源除外,如有侵权请联系站长!请勿违法!本站文章仅供学习了解!技术无罪!

kirin博客

排序算法主要分为10大类,他们的优缺点主要体现在时间复杂度和空间复杂度上,还有代码的难易程度上


这里我主要是对快速排序做一个再理解,因为在学习快速排序的时候遇到了一些问题,这些问题真的是很容易让人掉头发

快速排序的基本实现逻辑

在待排序数组中找一个基值,将比这个基值小的值移动到基值左边,将比这个基值大的值移动到基值右边,然后再将基值左右两边的数据重复次操作(递归),最后就能得到有序的一组数据

虽然听起来比较简单,但是我在理解的时候还是花费了一些时间

举一个例子

  1. 这是一个初始的数组:-10,20,15,1,0,30,-78,62,50
  2. 假设我们就取中间值0作为基值那么经过一次排序之后:-10,-78,0,1,20,15,30,62,50 (大概就是这种)
  3. 然后再将基值左边的数{-10,-78}进行操作:-78,-10
  4. 然后再将基值右边的数{1,20,15,30,62,50}进行操作:1, 15, 20, 30, 62, 50
  5. ...
  6. 最后得到:-78, -10, 0, 1, 15, 20, 30, 50, 62

这里面需要注意的点,我就是在这里被坑了,这里的基值不一定是中间值,你随便在数组中找一个来当做基值都可以,只不过找中间值的话可能更好理解(我并不觉得)

代码实现

  1. package com.quiteStore;
  2. import java.util.Arrays;
  3. public class QuiteStore {
  4. public static void main(String[] args) {
  5. int[] array = new int[]{-10,20,15,1,0,30,-78,62,50};
  6. QuikeSote.sote(array,0,array.length-1);
  7. }
  8. }
  9. //找到一个中间值(比较值)比较中间值两边值的大小将小的值放在左边,将大的值放在右边,一次进行这样的操作
  10. class QuikeSote{
  11. public static void sote(int[] array,int left,int right){
  12. //找到中间值(基值)
  13. int medianIndex = (left + right) / 2;
  14. int median = array[medianIndex];
  15. int temp = 0;
  16. //比较两边值的大小,从左边找到一个大的值,右边找到一个小的值,将这两个值交换,
  17. //特殊情况:左边的值都是小的,右边的值都是大的,此时就找完一轮
  18. while(left < right){
  19. while(array[left]<median && left <= right){
  20. left++;
  21. }
  22. //出循环说明找到了>=median的值
  23. while(array[right]>median && left <= right){
  24. right--;
  25. }
  26. //出循环说明找到了<=median的值
  27. //如果左下表和右下标相遇说明这一轮已经找完,那么就将基值和左下标或右下标对应的值进行交换,因为有一种特殊情况会使得基值发生改变
  28. //如果没有特殊情况交换之后也没事,因为左右下标所对应的值就是基值
  29. if(left>=right){
  30. temp = array[left];
  31. array[left] = median;
  32. median = temp;
  33. break;
  34. }
  35. //交换两个值
  36. temp = array[left];
  37. array[left] = array[right];
  38. array[right] = temp;
  39. //将右下标前移一位,因为右下标对应的值就是median,没必要进行再次比较,可能出现死循环
  40. if(array[left] == median){
  41. right--;
  42. }
  43. //将右下标前移一位,因为左下标对应的值就是median,没必要进行再次比较,可能出现死循环
  44. if(array[right] == median){
  45. left++;
  46. }
  47. System.out.println(Arrays.toString(array));
  48. //左递归
  49. QuikeSote.sote(array,0,left-1);
  50. //右递归
  51. QuikeSote.sote(array,right+1, array.length-1);
  52. }
  53. }

从执行图中也可以看出

最后哪一行就是最终结果

分享到:
加入交流群
未经允许不得转载:

作者: Bee, 转载或复制请以 超链接形式 并注明出处 Kirin博客
原文地址: 《Java快速排序》 发布于2022-2-14

切换注册

登录

您也可以使用第三方帐号快捷登录

切换登录

注册

觉得文章有用就加入交流群吧

QQ扫一扫