五种常见排序算法的总结

客官°小女子只卖身不卖艺 2022-05-10 13:48 239阅读 0赞

本文总结了一下五种常见的排序算法:选择排序、冒泡排序、插入排序、快速排序、堆排序。为方便理解记忆，以**升序**为例，先通过图形化排序过程来解释排序算法的实现原理，然后通过Java代码来实现排序。 （图源来自网络）

--------------------

1.  **选择排序**
    
    >  选择排序的原理十分简单直观，通常使用两层 for 循环来实现：第一层 for 循环依次选定数组从 0 到 N 的每一个索引位置的值，第二层 for 循环将该索引后的每个值依次与该索引的值进行比较，将较小值交换到第一层循环索引所在的位置。这就使得第一层 for 每一次循环都是在将剩余数组的最小值排列在剩余数组的最前列，最终实现升序排列。  
    > 时间复杂度为 O(N^2) 
    
      
    **选择排序的图形化排序过程：**  
      
    ![在这里插入图片描述][70]  
      
    **选择排序代码实现：**  
    
    
        public void selectSort(int[] arr) { 
        	//第一层for循环的arr[i]每次循环之后都会填入i之后的位置的最小值
           for (int i = 0; i < arr.length - 1; i++) { //有序区
           		//将arr[i]之后每一个值依次与arr[i]比较，若较小则交换，保证arr[i]的值最小
               for (int j = i + 1; j < arr.length; j++) { //无序区
                   if (arr[i] > arr[j]) { 
                       int temp = arr[i];
                       arr[i] = arr[j];
                       arr[j] = temp;
                   }
               }
           }
        ｝
    
      
    **创建一个长度为10万的随机数数组，测试5次选择排序花费的时间如下：**  
      
    ![在这里插入图片描述][70 1]
2.  **冒泡排序**
    
    >  冒泡排序同样使用双层 for 循环，第二层循环从 0 到 N 将相邻索引位置的值两两对比，将较大值交换到后一位，第二层循环遍历完成，就将无序区的最大值推到了数组最后。第一层循环重复冒泡过程，将无序区的最大值依次交换到数组右边的有序区，最终实现升序排列。  
    > 时间复杂度为 O(N^2) 
    
      
    **冒泡排序的图形化排序过程：**  
      
    ![在这里插入图片描述][70 2]  
      
    **冒泡排序代码实现：**  
    
    
        public static void bubbleSort(int[] arr) { 
            for (int i = 0; i < arr.length - 1; i++) { 
            	//将无序区的最大值移动到最右的有序区
                for (int j = 0; j < arr.length - 1 - i; j++) { 
                	//如果左边的值大于右边的值，则互换位置
                    if (arr[j] > arr[j + 1]) { 
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    
      
    **创建一个长度为10万的随机数数组，测试5次冒泡排序花费的时间如下：**  
      
    ![在这里插入图片描述][70 3]
3.  **插入排序**
    
    >  插入排序的原理是将数组中索引 0 既定为有序区，然后把索引 1 的值取出设定为插入值，将插入值和索引 0 的值对比，如果索引 0 的值较大，则把索引 0 的值往后移动一位，插入值到空出的位置，则索引 0 和索引 1 就是有序的。接着把索引 2 的值作为插入值依次往前对比，如果前面的值较大，则该值往后移动一位，直到找到一个更小值，将插入值放置到更小值之后，又形成了一个有序区。以此类推，最终整个数组都变成有序。  
    > 时间复杂度为 O(N^2) 
    
      
    **插入排序的图形化排序过程：**  
      
    ![在这里插入图片描述][70 4]  
      
    **插入排序代码实现：**  
    
    
        public static void insertSort(int[] arr) { 
           // j:插入位置的指针,insertNote:要插入的数据
            int j, insertNote;
        
            // 从数组的第二个元素开始循环将数组中的元素插入
            for (int i = 1; i < arr.length; i++) { 
                // 设置数组中的第2个元素为第一次循环要插入的数据
                insertNote = arr[i];
                j = i - 1;
                while (j >= 0 && insertNote < arr[j]) { 
                    // 如果要插入的元素小于第j个元素,就将第j个元素向后移动
                    arr[j + 1] = arr[j];
                    // 将j-1,开始判断前一位与插入值的大小
                    j--;
                }
                // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
                arr[j + 1] = insertNote;
            }
        }
    
      
    **创建一个长度为10万的随机数数组，测试5次插入排序花费的时间如下：**  
      
    ![在这里插入图片描述][70 5]
4.  **快速排序**
    
    >  快速排序的原理是在数组中随机取一个基准数，一个最左索引 i 和一个最右索引 j 。从索引 j 开始往左找到第一个小于基准值的值，将其赋值给 arr\[i\] ，然后将 i 往右移动一格；接着从索引 i 开始往右找到第一个大于基准值的值，将其赋值给 arr\[j\] ，并把 j 往左移动一格。依此类推，当 i 和 j 索引重合时停止，最后将基准值赋值给 arr\[i\] ，至此 i 左边的值都比 i 小，i 右边的值都比 i 大 ，接着使用递归将左右两边的子数组分别进行快速排序，最终得到一个有序数组。  
    > 时间复杂度为 O(N\*logN) 
    
      
    **快速排序的图形化排序过程：**  
      
    ![在这里插入图片描述][70 6]  
      
    **快速排序代码实现：**  
    
    
        public static void quickSort(int[] arr) { 
            if (arr.length == 0) return;
            quickSort(arr, 0, arr.length - 1);
        }
        
        private static void quickSort(int[] arr, int low, int high) { 
            if (low >= high) return;
            //取左边的数作为基准数
            int i = low, j = high, index = arr[i];
            //i==j时跳出循环
            while (i < j) { 
                //从最右开始向左寻找第一个小于index的数
                while (i < j && arr[j] >= index) j--;
                //将arr[j]放入arr[i],并将i右移
                if (i < j) arr[i++] = arr[j];
                //从最左开始向右寻找第一个大于index的数
                while (i < j && arr[i] <= index) i++;
                //将arr[i]放入arr[j],并将j左移
                if (i < j) arr[j--] = arr[i];
            }
            //最后将基数填入i
            arr[i] = index;
            //至此 , i左边都比i小 ,i右边都比i大
            quickSort(arr, low, i - 1);//递归,分治i左边
            quickSort(arr, i + 1, high);//递归,分治i右边
        }
    
      
    **创建一个长度为10万的随机数数组，测试5次快速排序花费的时间如下：**  
      
    ![在这里插入图片描述][70 7]
5.  **堆排序**
    
    >  堆排序的原理是建立一个完全二叉树，将数组的值填入其中，然后从右往左从下往上依次调整堆结构，使父节点的值不小于其两个子节点的值，一轮调整过后，根结点的键值就是所有堆结点键值中最大者。 
    
    ![在这里插入图片描述][70 8]
    
    >  接着将根节点的值与最后一个叶子节点的值互换，并将得到最大值的叶子节点从二叉树中取出，置入数组的最后，然后再次调整堆结构，依次类推，最终得到一个有序数组。 
    
    ![在这里插入图片描述][70 9]  
    ![在这里插入图片描述][70 10]  
    ![在这里插入图片描述][70 11]  
    ![在这里插入图片描述][70 12]  
    ![在这里插入图片描述][70 13]
    
    >  时间复杂度为 O(N\*logN) 
    
      
    **堆排序的图形化排序过程：**  
      
    ![在这里插入图片描述][70 14]  
      
    **堆排序代码实现：**  
    
    
        public static void heapSort(int[] arr) { 
            //1.构建大顶堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) { 
                //从第一个非叶子结点从下至上，从右至左调整结构
                adjustHeap(arr, i, arr.length);
            }
            //2.调整堆结构+交换堆顶元素与末尾元素
            for (int j = arr.length - 1; j > 0; j--) { 
                swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
                adjustHeap(arr, 0, j);//重新对堆进行调整
            }
        }
        
        //调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
        public static void adjustHeap(int[] arr, int i, int length) { 
            int temp = arr[i];//先取出当前元素i
            for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { //从i结点的左子结点开始，也就是2i+1处开始
                if (k + 1 < length && arr[k] < arr[k + 1]) { //如果左子结点小于右子结点，k指向右子结点
                    k++;
                }
                if (arr[k] > temp) { //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                    arr[i] = arr[k];
                    i = k;
                } else { 
                    break;
                }
            }
            arr[i] = temp;//将temp值放到最终的位置
        }
        
        //交换元素
        public static void swap(int[] arr, int a, int b) { 
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    
      
    **创建一个长度为10万的随机数数组，测试5次堆排序花费的时间如下：**  
    ![在这里插入图片描述][70 15]

[70]: /images/20220505/5e1da6361b34438292b3877a84be5cfd.png
[70 1]: /images/20220505/a7a5f669e1c545efafa9577442ee9b27.png
[70 2]: /images/20220505/339d6f87fdef4c2b84f01919f92aec4c.png
[70 3]: /images/20220505/d0579b21052b49d1a3938958e61194cc.png
[70 4]: /images/20220505/ad5eee09ada34fb3a8a7691847bdbe31.png
[70 5]: /images/20220505/5fcdab56c904482daeffdcd265adc1c8.png
[70 6]: /images/20220505/8cabe303a9564fd29e52f16fe6dde2f8.png
[70 7]: /images/20220505/39f02fdc8c174314b0f9e04973ce6102.png
[70 8]: /images/20220505/44eba565fa4f48a98d3eec19a5f426f9.png
[70 9]: /images/20220505/02c3e864383d41eeb0266b942795208b.png
[70 10]: /images/20220505/db31bbbb28464c44abf43ae86b03c0b0.png
[70 11]: /images/20220505/7ca80d2769c84244aaccbbfe879d2d9a.png
[70 12]: /images/20220505/90d8445912ff488c94049028228e9ca1.png
[70 13]: /images/20220505/12a9784c58e44943a1a0ea1438b216e8.png
[70 14]: /images/20220505/e2eb2b9e345b4b1999e4084ba2a1fbea.png
[70 15]: /images/20220505/27145d2fcc9c49339236bfd0638028dc.png