【数据结构】七大排序详解(贰)——冒泡排序、快速排序、归并排序

男娘i 2024-04-17 10:36 66阅读 0赞

#### 文章目录 ####

*  ⚽冒泡排序
 *   *  ⚾算法步骤
     *  ?算法优化
     *  ?代码实现：
     *  ?冒泡排序的特性总结
 *  ?快速排序
 *   *  ⚽算法思路
     *   *  ?思路一（Hoare版）
         *  ?思路二（挖坑法）
         *  ?思路三（前后指针）
     *  ?代码实现：
     *  ?快速排序优化
     *   *  ?规模较小时的优化
         *  ?三数取中法
     *  ?快速排序非递归实现
     *   *  ?代码实现：
     *  ?快速排序特性总结
 *  ?归并排序
 *   *  ⚽基本思想
     *  ?算法步骤
     *  ?代码实现：
     *  ?递归实现归并排序
     *  ?归并排序特性总结
     *  ?海量数据的排序问题
 *  ??排序算法复杂度及稳定性分析
 *  ⭕总结

## ⚽冒泡排序 ##

==冒泡排序（Bubble Sort）==也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

### ⚾算法步骤 ###

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

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

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

![在这里插入图片描述][075f710f19866c56ddcbef32f999a21f.gif]

### ?算法优化 ###

冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序

直接返回就好

### ?代码实现： ###

public  int[] bubbleSort(int[] arr) {
        
            int[] array = Arrays.copyOf(arr,arr.length);
            for(int i = 1;i < array.length ; i ++) {
        
                Boolean a = true;
                for(int j = 0; j < array.length - i; j++) {
        
                    if(array[j] > array[j + 1]) {
        
                        swap(array,j,j+1);
                        a = false;
                    }
                }
                if(a) {
        
                    return array;
                }
            }
            return array;
        }
        private void swap (int[] arr,int m,int n) {
        
            int tmp = arr[m];
            arr[m] = arr[n];
            arr[n] = tmp;
        }

### ?冒泡排序的特性总结 ###

1.  冒泡排序是一种非常容易理解的排序
2.  时间复杂度：O(N^2)
3.  空间复杂度：O(1)
4.  稳定性：稳定
5.  什么时候最快  
    当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。
6.  什么时候最慢  
    当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

## ?快速排序 ##

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：***任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止***

### ⚽算法思路 ###

#### ?思路一（Hoare版） ####

步骤为：

1.  选取基准值
2.  从数组右->左找到比基准值小于或等于的值的下标
3.  从数组右->左找到比基准值大于或等于的值的下标
4.  交换这两下标的值
5.  继续执行二操作，直到操作2与操作3相遇
6.  将基准值放在相遇位置

如下图所示：

![在这里插入图片描述][20210515134431451.gif_pic_center_23pic_center]

#### ?思路二（挖坑法） ####

步骤为：

1.  选取基准值后，记录下基准值，假设该下标为空，相当于是个“坑”
2.  从右->左找小于或等于基准值的值，就将该数放入坑中，然后该下标变为新的坑
3.  从左->右找小于或等于基准值的值，就将该数放入坑中，然后该下标变为新的坑
4.  回到步骤2继续执行，直到操作2与操作3所找数相同
5.  将记录下的基准值放回坑里

图示如下：  
![在这里插入图片描述][4a1cb0aa5a6248aaad769c5b5be9a410.gif]

#### ?思路三（前后指针） ####

步骤及其动图如下：  
![在这里插入图片描述][20210515172409754.gif_pic_center]

### ?代码实现： ###

public int[] quickSort(int[] array) {
        
            int[] arr = Arrays.copyOf(array,array.length);
            int left = 0;
            int right = arr.length - 1;
            quick(arr,left,right);
            return arr;
        }
        private void quick(int[] array,int begin,int end) {
        
            if(begin >= end) {
        
                return;
            }
            int centre = partition1(array,begin,end);
            //int centre = partition2(array,begin,end);
            //int centre = partition3(array,begin,end);
            quick(array,centre + 1,end);
            quick(array,begin,centre - 1);
        }
        //挖坑法
        private  int partition1(int[] array,int left,int right) {
        
            int tmp = array[left];
            while (left < right) {
        
                while (left< right && array[right] >= tmp) {
        
                    right--;
                }
                array[left] = array[right];
                while (left< right && array[left] <= tmp) {
        
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = tmp;
            return left;
        }
        //Hoare版
        private  int partition2(int[] array,int left,int right) {
        
            int tmp = array[left];
            int i = left;
            while (left < right) {
        
                while (left< right && array[right] >= tmp) {
        
                    right--;
                }
                while (left< right && array[left] <= tmp) {
        
                    left++;
                }
                swap(array,left,right);
            }
            swap(array,left,i);
            return left;
        }
        //前后指针法
        private int partition3(int[] array,int left,int right) {
        
            int prev = left ;
            int cur = left+1;
            while (cur <= right) {
        
                if(array[cur] < array[left] && array[++prev] != array[cur]) {
        
                    swap(array,cur,prev);
                }
                cur++;
            }
            swap(array,prev,left);
            return prev;
        }
        private void swap (int[] arr,int m,int n) {
        
            int tmp = arr[m];
            arr[m] = arr[n];
            arr[n] = tmp;
        }

### ?快速排序优化 ###

#### ?规模较小时的优化 ####

每次递归的时候，数据都是再慢慢变成有序的

当数据量少且趋于有序的时候，我们可以直接使用插入排序进行优化

private void quick(int[] array,int begin,int end) {
        
            if(begin >= end) {
        
                return;
            }
            if(end - begin < 20) {
        
                //插入排序
                //......
                return;
            }
            int centre = partition1(array,begin,end);
            //int centre = partition2(array,begin,end);
            //int centre = partition3(array,begin,end);
            quick(array,centre + 1,end);
            quick(array,begin,centre - 1);
        }

#### ?三数取中法 ####

如果在选取基数时我们发现如果基数一边总是没有数，代码的执行次数会增加很多

所以我们的解决方法为：  
选取数组第一个数、中间的数、和最后一个数，进行比较

三数中间的数作为每次的基数

寻找中间数代码如下：

private  int midThree(int[] array,int left,int right) {
        
            int mid = (left + right) / 2;
            //6  8
            if (array[left] < array[right]) {
        
                if (array[mid] < array[left]) {
        
                    return left;
                } else if (array[mid] > array[right]) {
        
                    return right;
                } else {
        
                    return mid;
                }
            } else {
        
                //array[left] > array[right]
                if (array[mid] < array[right]) {
        
                    return right;
                } else if (array[mid] > array[left]) {
        
                    return left;
                } else {
        
                    return mid;
                }
            }
        }

使用如下：

private  int partition1(int[] array,int left,int right) {
        
            int tmp = midThree(array,left,right);
            while (left < right) {
        
                while (left< right && array[right] >= tmp) {
        
                    right--;
                }
                array[left] = array[right];
                while (left< right && array[left] <= tmp) {
        
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = tmp;
            return left;
        }
        //Hoare版
        private  int partition2(int[] array,int left,int right) {
        
            int tmp = midThree(array,left,right);
            int i = left;
            while (left < right) {
        
                while (left< right && array[right] >= tmp) {
        
                    right--;
                }
                while (left< right && array[left] <= tmp) {
        
                    left++;
                }
                swap(array,left,right);
            }
            swap(array,left,i);
            return left;
        }

### ?快速排序非递归实现 ###

实现思路：

*  建立一个栈
 *  先让一组数据的起点入栈
 *  再让一组数据的终点出栈
 *  ![在这里插入图片描述][a7772ff0c45d4a3cabedc266a83beeb3.png]
 *  然后两次出栈，分别作为该数据的起点与终点
 *  然后经过我们上面所写的方法进行排序后
 *  再将两组数据进行入栈
 *  ![在这里插入图片描述][a864661ee4d8424b8b6261fbef1336ac.png]
 *  以此循环直到栈为空

#### ?代码实现： ####

//快速排序递归实现
        public int[] quickSortPlus(int[] array) {
        
            int[] arr = Arrays.copyOf(array,array.length);
            Deque<Integer> stack = new LinkedList<>();
            int left = 0;
            int right = array.length-1;
            int pivot = 0;
            stack.push(left);
            stack.push(right);
            while (!stack.isEmpty()) {
        
                right= stack.pop();
                left = stack.pop();
                pivot = partition(arr,left,right);
                if(pivot > left+1) {
        
                    stack.push(left);
                    stack.push(pivot-1);
                }
                if(pivot < right-1) {
        
                    stack.push(pivot+1);
                    stack.push(right);
                }
            }
            return arr;
        }
        private  int partition(int[] array,int left,int right) {
        
            int tmp = array[left];
            while (left < right) {
        
                while (left< right && array[right] >= tmp) {
        
                    right--;
                }
                array[left] = array[right];
                while (left< right && array[left] <= tmp) {
        
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = tmp;
            return left;
        }

### ?快速排序特性总结 ###

1.  快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2.  时间复杂度：O(N\*logN)  
    ![在这里插入图片描述][bf256099674b419391f83151df7ce2c8.png]
3.  空间复杂度：O(logN)
4.  稳定性：不稳定

## ?归并排序 ##

### ⚽基本思想 ###

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and  
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：  
![在这里插入图片描述][15b1ec17ef104e8caf696004d96f10c9.png]

### ?算法步骤 ###

1.  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.  设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.  重复步骤 3 直到某一指针达到序列尾；
5.  将另一序列剩下的所有元素直接复制到合并序列尾。

![在这里插入图片描述][8a1078cdfd74e0e8731ddd43bd417f2e.gif]

### ?代码实现： ###

public  void mergeSort1(int[] array) {
        
            mergeSortFunc(array,0,array.length-1);
        }
        private  void mergeSortFunc(int[] array,int left,int right) {
        
            if(left >= right) {
        
                return;
            }
    
            int mid = (left+right) / 2;
            mergeSortFunc(array,left,mid);
            mergeSortFunc(array,mid+1,right);
            merge(array,left,right,mid);
        }
    
        private  void merge(int[] array,int start,int end,int mid) {
        
            int s1 = start;
            //int e1 = mid;
            int s2 = mid+1;
            //int e2 = end;
            int[] tmp = new int[end-start+1];
            int k = 0;//tmp数组的下标
            while (s1 <= mid && s2 <= end) {
        
                if(array[s1] <= array[s2]) {
        
                    tmp[k++] = array[s1++];
                }else {
        
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= mid) {
        
                tmp[k++] = array[s1++];
            }
            while (s2 <= end) {
        
                tmp[k++] = array[s2++];
            }
    
            for (int i = 0; i < tmp.length; i++) {
        
                array[i+start] = tmp[i];
            }
    	}

### ?递归实现归并排序 ###

public static void mergeSort(int[] array) {
        
            int gap = 1;
            while (gap < array.length) {
        
                // i += gap * 2 当前gap组的时候，去排序下一组
                for (int i = 0; i < array.length; i += gap * 2) {
        
                    int left = i;
                    int mid = left+gap-1;//有可能会越界
                    if(mid >= array.length) {
        
                        mid = array.length-1;
                    }
                    int right = mid+gap;//有可能会越界
                    if(right>= array.length) {
        
                        right = array.length-1;
                    }
                    merge(array,left,right,mid);
                }
                //当前为2组有序  下次变成4组有序
                gap *= 2;
            }
        }
        private  void merge(int[] array,int start,int end,int mid) {
        
            int s1 = start;
            //int e1 = mid;
            int s2 = mid+1;
            //int e2 = end;
            int[] tmp = new int[end-start+1];
            int k = 0;//tmp数组的下标
            while (s1 <= mid && s2 <= end) {
        
                if(array[s1] <= array[s2]) {
        
                    tmp[k++] = array[s1++];
                }else {
        
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= mid) {
        
                tmp[k++] = array[s1++];
            }
            while (s2 <= end) {
        
                tmp[k++] = array[s2++];
            }
    
            for (int i = 0; i < tmp.length; i++) {
        
                array[i+start] = tmp[i];
            }
    	}

### ?归并排序特性总结 ###

1.  归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.  时间复杂度：O(N\*logN)
3.  空间复杂度：O(N)
4.  稳定性：稳定

### ?海量数据的排序问题 ###

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有 1G，需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1.  先把文件切分成 200 份，每个 512 M
2.  分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3.  进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

## ??排序算法复杂度及稳定性分析 ##

![在这里插入图片描述][a31c8b35d8924548b726112da2eaf717.png]  
![在这里插入图片描述][bcc8ebbe53cc472f9012e8ba7fbae9f2.png]

## ⭕总结 ##

关于《【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[075f710f19866c56ddcbef32f999a21f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c633f2b46ad44a5c97e78683d804dd50.gif
[20210515134431451.gif_pic_center_23pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b0663deb27a145b4baa820e97f4bf13c.gif
[4a1cb0aa5a6248aaad769c5b5be9a410.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/cd579422279c49da870faf4070cc22e0.gif
[20210515172409754.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c01f135091364fec97cdcf817c0576c2.gif
[a7772ff0c45d4a3cabedc266a83beeb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ece6ccf915424eca85215ef3f422fdc5.png
[a864661ee4d8424b8b6261fbef1336ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4ed79edf9fc14dd682c8b0b84505b883.png
[bf256099674b419391f83151df7ce2c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/46bc5c3f5092417c898ecfb855f8f8b0.png
[15b1ec17ef104e8caf696004d96f10c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/78103221ed6943cf8417f3da7aa07506.png
[8a1078cdfd74e0e8731ddd43bd417f2e.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/7a8239286cac4172a5696b08344db9cc.gif
[a31c8b35d8924548b726112da2eaf717.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/91b11530c89241d69bd27f718a7b68c6.png
[bcc8ebbe53cc472f9012e8ba7fbae9f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4808e9b49f9245148e7d0c3ffa28b903.png