devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

冒泡排序&快速排序（前后指针、挖坑、左右指针法）【Java实现】_冒泡排序法左指针和右指针和基准元素

作者：木道寻08 | 2024-07-02 20:38:18

赞

踩

冒泡排序法左指针和右指针和基准元素

一、冒泡排序

思想：

对N个元素进行升序排列时，依次比较两个相邻的元素，如果前者大于后者就交换，一趟排序找出一个最大值并放在最后，然后缩小排序区间继续找出该区间的最大值，并放在倒数第二个位置，倒数第一个位置...，直到区间缩小至只剩一个元素，排序完成。整个排序过程要进行N-1趟排序。

原理：

1.比较相邻的元素。如果前者比后者大，就交换他们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

待排序序列：  2    5    7    1    3    7

第一趟排序：

2   5   7   1   3   7     ->    2   5   7   1   3   7

2   5   7   1   3   7     ->    2   5   7   1   3   7 

2   5   7   1   3   7     ->    2   5   1   7   3   7

2   5   1   7   3   7     ->    2   5   1   3   7   7

2   5   1   3   7   7     ->    2   5   1   3   7   7

第一趟排序后的序列：2   5   1   3   7   7

第二趟排序：

2   5   1   3   7     ->     2   5   1   3   7

2   5   1   3   7     ->     2   1   5   3   7 

2   1   5   3   7     ->     2   1   3   5   7

2   1   3   5   7     ->     2   1   3   5   7

第二趟排序后的序列：2   1   3   5   7   7 

第三趟排序：

2   1   3   5     ->     1   2   3   5

1   2   3   5     ->     1   2   3   5

1   2   3   5     ->     1   2   3   5

第三趟排序后的序列：1   2   3   5   7   7

第四趟排序：

1   2   3     ->     1   2   3

1   2   3     ->     1   2   3

第四趟排序后的序列：1   2   3   5   7   7

第五趟排序：

1   2     ->     1   2

第五趟排序后的序列：1   2   3   5   7   7

排序完成！

注意：

假如给定待排序序列已经有序，如{1,2,4,5,6,7}，那么第一次排序便不会交换相邻元素。后续比较排序也是。所以，为了减少已经有序的待排序序列的排序时间，我们可以设置一个标志位flag，初值为false。如果某一次排序过程中有交换元素，便将flag置为true。下一次排序之前又将flag置为1；如果此次排序完成flag仍为1，说明此次排序没有交换任何元素，那么证明该序列已经有序，则不需要再继续进行排序。整个排序过程就完成了。所以最多可进行n-1趟排序。

  1. public class BubbleSort {
  2.     private int[] arr;
  3.     private int len;
  4.  
  5.  
  6.     public BubbleSort(int[] arr) {
  7.         this.arr = arr;
  8.         this.len = arr.length;
  9.     }
  10.  
  11.  
  12.     public void bubbleSort() {
  13.         for (int i = len - 1; i > 0; i--) {//len个元素，总共进行len-1趟排序
  14.             boolean flag = false;//标识此趟排序是否有元素交换了位置，flag为false表示没交换
  15.             for (int j = 0; j < i; j++) {//每进行完一趟排序，将要排序的区间缩小1个元素
  16.                 if (arr[j] > arr[j + 1]) {
  17.                     swap(j, j + 1);
  18.                     flag = true;//有元素交换，flag置为true
  19.                 }
  20.             }
  21.             //如果一趟排序下来flag一直为false，表明此趟排序没有元素交换位置，说明此时数组已经有序，可结束排序
  22.             if (flag == false) {
  23.                 return;
  24.             }
  25.         }
  26.     }
  27.  
  28.     public void swap(int i, int j) {
  29.         int tmp = arr[i];
  30.         arr[i] = arr[j];
  31.         arr[j] = tmp;
  32.     }
  33.  
  34.     public void print() {
  35.         for (int i = 0; i < len; i++) {
  36.             System.out.print(arr[i] + " ");
  37.         }
  38.         System.out.println("");
  39.     }
  40.  
  41. }

稳定性判断：

因为冒泡排序是不断把大的元素往后调的过程，此过程是不断比较相邻元素并交换的过程，所以如果两个相邻元素相等的话，我们并不会交换它俩的位置；如果两个元素相等不相邻的话，就算通过交换会将两个相等元素调到相邻，此时我们也不会交换它俩的位置，所以排序前后相同元素的位置顺序并没有改变，所以冒泡排序是一个稳定的排序算法。 

测试类代码如下： 

  1. package com.myself.sort;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class TestSort {
  6.     public static void main(String[] args) {
  7.         Scanner scanner = new Scanner(System.in);
  8.         while (scanner.hasNext()) {
  9.             int len = scanner.nextInt();
  10.             int[] arr = new int[len];
  11.             for (int i = 0; i < len; i++) {
  12.                 arr[i] = scanner.nextInt();
  13.             }
  14.             //冒泡排序
  15.             BubbleSort sortArr = new BubbleSort(arr);
  16.             sortArr.bubbleSort();
  17.             sortArr.print();
  18.         }
  19.     }
  20. }

二、快速排序

快速排序是对冒泡排序的一种改进。

思想：

通过选择一个基准值将要排序的数据分成两个区间，其中一个区间的所有元素都比基准值小，另一个区间的所有元素都比基准值大。然后采用分而治之的方法对这两部分数据分别进行快速排序，当区间中只剩一个数或者为空时停止此次排序，以此达到整个数据变成有序序列。

快排主要有3种实现方法：hoare法，又称左右指针法；挖坑法；前后指针法（现为了简便，下面三种方法均以区间右端点所在元素作为基准值）

左右指针法：定义两个指针begin和end，其初值分别为待排序区间左端点、右端点，begin从左往右走，寻找比基准值小或等的元素，end从右往左走，寻找比基准值大或等的元素。当begin停下时，表面此时的元素大于基准值；当end停下时，表面此时的元素小于基准值。此时交换对应的两个元素，继续上述过程。最后当begin和end相等时，交换其中一个元素和基准值，并返回基准值此时的下标。

以数组{2,9,3,6,7,5}为例，具体排序过程如下图所示

此时基准值5将区间分成两个小区间 ，一个区间内的元素都小于等于5，另一个区间内的元素都大于等于5。

左区间排序如下：

右区间排序如下：

代码实现如下：

  1. //1. 左右指针法
  2.     private int parition1(int left, int right) {
  3.         int begin = left;
  4.         int end = right;
  5.         while (begin < end) {
  6.             while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写，因为如果区间本身已经有序，begin会一直往右走，直到走到end，还会继续往右走
  7.                 begin++;
  8.             }
  9.             //此时begin所指向的元素比基准值大
  10.             while ((begin < end) && (arr[end] >= arr[right])) {//同理，此步的begin<end也一定要写
  11.                 end--;
  12.             }
  13.             //此时end所指向的元素比基准值小
  14.             swap(begin, end);//交换begin和end所指向的元素
  15.         }
  16.         swap(begin,right);
  17.         return begin;
  18.     }

挖坑法：先将基准值保存起来，此时相当于基准值的位置就空出来了。然后定义两个指针begin和end，其初始值分别为待排序区间的左端点和右端点，begin寻找比基准值大的元素，end寻找比基准值小的元素。当begin找到比基准值大的元素之后，此时将其赋给end所指位置，那么begin所指位置便又空出来了；当end找到比基准值小的元素之后，此时将其赋给begin所指位置，那么此时end所指位置又空出来了。重复上述过程，直到begin==end。此时将基准值赋给begin所指位置并返回下标begin。

以{2,9,3,6,7,5}为例，具体排序过程如下

此时基准值5将区间分成了两个小区间，其中左区间的元素全部小于等于5，右区间的元素全部大于等于5

其中左区间排序如下：

右区间排序如下：

代码实现如下： 

  1. //2. 挖坑法
  2.     private int parition2(int left, int right) {
  3.         int key = arr[right];//记录基准值
  4.         int begin = left;
  5.         int end = right;
  6.         while (begin < end) {
  7.             while ((begin < end) && (arr[begin] <= key)) {
  8.                 begin++;
  9.             }
  10.             //此时begin所指向的值比基准值大
  11.             arr[end] = arr[begin];
  12.             while ((begin < end) && (arr[end] >= key)) {
  13.                 end--;
  14.             }
  15.             arr[begin] = arr[end];
  16.         }
  17.         arr[begin] = key;
  18.         return begin;
  19.     }

前后指针法：定义两个指针div和cur，初始值均为待排序区间的左端点，其中div所指位置之前表示比基准值小或等的元素，div和cur之间表示比基准值大的元素，cur之后表示待排序部分。在cur遍历整个待排序区域期间，如果cur所指元素小于div所指元素，则交换，此时div++。最后交换div所指元素和基准值，并返回基准值此时的下标。

以数组{2,9,3,6,7,5}为例

此时5将区间分成了两个小区间，分别对两个小区间按同样的方法进行排序。

左区间排序如下所示：

右区间排序如下所示：

代码实现如下： 

  1. //3. 前后指针法
  2.     private int parition3(int left, int right) {
  3.         int div = left;
  4.         int cur;
  5.         for (cur = left; cur < right; cur++) {
  6.             if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值，并让div往右走一步，以保证div之前的值都小于等于基准值
  7.                 swap(div, cur);
  8.                 div++;
  9.             }
  10.         }
  11.         //此时cur=right
  12.         swap(div, cur);
  13.         return div;
  14.     }

快速排序三种方法完整代码如下： 

  1. public class QuickSort {
  2.     private int[] arr;
  3.     private int len;
  4.  
  5.     public QuickSort(int[] arr) {
  6.         this.arr = arr;
  7.         this.len = arr.length;
  8.     }
  9.  
  10.     public void quickSort() {
  11.         __quickSort(0, len - 1);
  12.     }
  13.  
  14.     private void __quickSort(int left, int right) {
  15.         if (left == right) {//区间只剩一个元素的情况下不用再进行排序
  16.             return;
  17.         }
  18.         if (left > right) {//区间没有元素了
  19.             return;
  20.         }
  21.         int div = parition3(left, right);
  22.         __quickSort(left, div - 1);
  23.         __quickSort(div + 1, right);
  24.     }
  25. //以下三种方法均以区间最后一个元素作为基准值
  26.  
  27.     //1. 左右指针法
  28.     private int parition1(int left, int right) {
  29.         int begin = left;
  30.         int end = right;
  31.         while (begin < end) {
  32.             while ((begin < end) && (arr[begin] <= arr[right])) {//此步的begin<end一定要写，因为如果区间本身已经有序，begin会一直往右走，直到走到end，还会继续往右走
  33.                 begin++;
  34.             }
  35.             //此时begin所指向的元素比基准值大
  36.             while ((begin < end) && (arr[end] >= arr[right])) {//同理，此步的begin<end也一定要写
  37.                 end--;
  38.             }
  39.             //此时end所指向的元素比基准值小
  40.             swap(begin, end);//交换begin和end所指向的元素
  41.         }
  42.         swap(begin,right);
  43.         return begin;
  44.     }
  45.  
  46.     //2. 挖坑法
  47.     private int parition2(int left, int right) {
  48.         int key = arr[right];//记录基准值
  49.         int begin = left;
  50.         int end = right;
  51.         while (begin < end) {
  52.             while ((begin < end) && (arr[begin] <= key)) {
  53.                 begin++;
  54.             }
  55.             //此时begin所指向的值比基准值大
  56.             arr[end] = arr[begin];
  57.             while ((begin < end) && (arr[end] >= key)) {
  58.                 end--;
  59.             }
  60.             arr[begin] = arr[end];
  61.         }
  62.         arr[begin] = key;
  63.         return begin;
  64.     }
  65.  
  66.     //3. 前后指针法
  67.     private int parition3(int left, int right) {
  68.         int div = left;
  69.         int cur;
  70.         for (cur = left; cur < right; cur++) {
  71.             if (arr[cur] <= arr[right]) {//遇到cur指向的值小于等于基准值就交换div和cur指向的值，并让div往右走一步，以保证div之前的值都小于等于基准值
  72.                 swap(div, cur);
  73.                 div++;
  74.             }
  75.         }
  76.         //此时cur=right
  77.         swap(div, cur);
  78.         return div;
  79.     }
  80.  
  81.     //交换两个元素的值
  82.     public void swap(int i, int j) {
  83.         int tmp = arr[i];
  84.         arr[i] = arr[j];
  85.         arr[j] = tmp;
  86.     }
  87.  
  88.     public void print() {
  89.         for (int i = 0; i < len; i++) {
  90.             System.out.print(arr[i] + " ");
  91.         }
  92.         System.out.println("");
  93.     }
  94. }

测试类代码如下： 

  1. package com.myself.sort;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class TestSort {
  6.     public static void main(String[] args) {
  7.         Scanner scanner = new Scanner(System.in);
  8.         while (scanner.hasNext()) {
  9.             int len = scanner.nextInt();
  10.             int[] arr = new int[len];
  11.             for (int i = 0; i < len; i++) {
  12.                 arr[i] = scanner.nextInt();
  13.             }
  14.             //快速排序
  15.             QuickSort quickSort=new QuickSort(arr);
  16.             quickSort.quickSort();
  17.             quickSort.print();
  18.         }
  19.     }
  20. }

稳定性判断：

由于以上三种方法实现快速排序的基本思想都一样，现以左右指针法为例，在左右指针begin和end不断向中间靠拢的过程中，只有begin遇到大于基准值或begin等于end的时候才会停下来，同样，end在遇到小于基准值或begin==end时也会停下来，此时进行begin和end所指元素交换操作，然后继续该过程，直到begin==end。此时交换begin所指元素和基准值，而该过程很有可能会把前面元素的稳定性打乱，以{2,9,3,6,5,5}为例，交换基准值5和9的位置，会让基准值（第二个5）跑到第一个5的前面，导致排序前后相同元素的前后顺序不一致，所以快速排序是一个不稳定的排序算法。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/780846
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号