Java版本排序算法总结

野性酷女 2022-06-07 02:58 181阅读 0赞

对排序算法总结，考研时本来很熟悉，过段时间很多细节又忘记了，写篇blog总结一下。

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

## **O（nlogn）** ##

**首先当n较大，则应采用时间复杂度为O(nlogn)的排序方法：快速排序、堆排序或归并排序。**  
**快速排序**：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

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

## **快速排序Quick Sort** ##

Arrays.sort（）方法底层就用的快速排序和插入排序，对于元素少的用插入排序，对于元素多的用快速排序。

**算法思想**  
1）选择一个基准元素,通常选择第一个元素  
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。  
3）此时基准元素在其排好序后的正确位置  
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。  
![这里写图片描述][SouthEast]  
**首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要**（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
同样交换 4 与 9.  
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]  
第一轮排序就结束了，接下来递归对6左右的数值排序  
**代码实现**

//left和right是想排序的数值下标范围
    public void quickSort(int[] arr,int left,int right){
            // 如果left不小于right，需要排序的部分只有一个元素，方法返回
            if(left >= right){
                return;
            }
            //设置最左边的元素为基准点：pivot
            int p = arr[left];
            //把要排序的序列中比p大的放到右边，比p小的放到左边，P的下标为i 
            int i =left;
            int j =right;
            while(i<j){
                //j向左移，找到一个比p小的元素
                while(arr[j]>=p && i<j){
                    j--;
                }
                //i向右移，找到一个比p大的元素
                while(arr[i]<=p && i<j){
                    i++;
                }
                //arr[i]和arr[j]交换
                if(i<j){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            arr[left] = arr[i];
            arr[i] = p;
            //对序列中，i左边的元素进行快速排序
            quickSort(arr,left,i-1);
            //对序列中，i右边的元素进行快速排序
            quickSort(arr,i+1,right);
        }

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

## **归并排序 Merge Sort** ##

**算法思想：**

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。  
![这里写图片描述][SouthEast 5]

设定两个指针，分别指着要合并的两个空间的第一个元素，从两个空间第一个元素开始比较元素的大小。较小的就放入合并空间中，指针向前移动。

**代码实现：**

public class MergeSort {   
        /** * 归并排序 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 * 时间复杂度为O(nlogn) * 稳定排序方式 * @param nums 待排序数组 * @return 输出有序数组 */  
        public static void mergeSort(int[] nums, int low, int high) {  
            int mid = low + (high - low)/2;
            if (low < high) {  
                // 左边 
                mergeSort(nums, low, mid);  
                // 右边 
                mergeSort(nums, mid + 1, high);  
                // 左右归并 
                merge(nums, low, mid, high);  
            } 
        }  
    
        public static void merge(int[] nums, int low, int mid, int high) {  
            int[] temp = new int[high - low + 1];  
            int i = low;// 左指针 
            int j = mid + 1;// 右指针 
            int k = 0;  
    
            // 把较小的数先移到新数组中 
            while (i <= mid && j <= high) {  
                if (nums[i] < nums[j]) {  
                    temp[k++] = nums[i++];  
                } else {  
                    temp[k++] = nums[j++];  
                }  
            }  
    
            // 把左边剩余的数移入数组 
            while (i <= mid) {  
                temp[k++] = nums[i++];  
            }  
    
            // 把右边边剩余的数移入数组 
            while (j <= high) {  
                temp[k++] = nums[j++];  
            }  
    
            // 把新数组中的数覆盖nums数组 
            for (int k2 = 0; k2 < temp.length; k2++) {  
                nums[k2 + low] = temp[k2];  
            }  
        }  
    
    
        // 归并排序的实现 
        public static void main(String[] args) {  
    
            int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  
    
            MergeSort.sort(nums, 0, nums.length-1);  
            System.out.println(Arrays.toString(nums));  
        }  
    }

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

## **堆排序 Heap Sort** ##

**算法思想：**  
堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。  
![这里写图片描述][SouthEast 6]  
大顶堆就是其任何一个非叶子节点都大于其左右孩子节点。

**代码实现：**

public static void adjustHeap(int[] a, int low, int high) {
        int i=low;
        int j=2*i;                             //a[j]是a[i]的左孩子节点
        int temp = a[i];
        while(j<=high){
            if(j<high && a[j]<a[j+1]){         //如果右孩子比较大，则把j指向右孩子
                 ++j;   
            }
            if(temp<a[j]){
                a[i] = a[j];
                i = j;                   //修改i和j的值，以便继续向下调整
                j=2*i;
            } else
                break;
        }
        a[i] = temp;                      //被调整的点放入最终位置
    }
    
    public static void heapSort(int[] a) {
        int i;
        int temp;
        for (i = a.length / 2 ; i >= 0; i--) {
       // 构建一个大顶堆
            adjustHeap(a, i, a.length - 1);
        }
        for (i = a.length - 1; i >= 0; i--) {
       // 将堆顶记录和当前未经排序子序列的最后一个记录交换，进行n-1次排序
            temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            adjustHeap(a, 0, i - 1);         // 将a中前i-1个记录重新调整为大顶堆
        }
    }
    
    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }

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

## **O（n2）** ##

平方阶(O(n2))排序各类简单排序

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

## **冒泡排序 Bubble Sort** ##

冒泡排序可以说是排序算法中最慢的一个，可以直观的看以下视屏感受一下几种排序算法的速度比较  
[9种排序算法在四种数据分布下的速度比较][9]

**算法思想：**  
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第2位上的数归位，依次类推。  
每次都是比较相邻的两个数，如果前面的的数比后面的数大，则交换这两个数的位置，一直比较下去直到最后两个数比较完毕后，最大的数就在最后一个了。这就是它的最终位置。  
![这里写图片描述][SouthEast 7]

**代码实现：**

public void bubbleSort(int a[]){  
        for(int i =0 ; i< arr.length-1; ++i) {
           // 找出数组中最大的数字，排到最后 
            for(int j = 0; j < arr.length-i-1; ++j) {  
                if(a[j] > a[j+1])  
                {  
                    int temp = a[j] ; 
                    a[j] = a[j+1] ; 
                    a[j+1] = temp;  
                }  
            }  
        }  
    }

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

## **插入排序 Insertion Sort** ##

**算法思想：**  
插入排序的算法思想很简单，就和我们打扑克牌起牌时一样，我们手中有一些牌，是排好序的，每次我们再从牌堆里起牌，就会把起到的牌插入到手牌中来，这就叫插入排序。  
![这里写图片描述][SouthEast 8]

我们以下标为0的基准，认为第一个数为有序的部分，以下标为1的开始依次往前插入，一个一个插入，排好序的部分就越来越多，直到最后一个元素也插入到前面  
![这里写图片描述][SouthEast 9]

插入时插入的值赋为temp，从右往左依次比较，如果元素大于temp，就向后移一位，如果元素小于temp，就插入在它后面。  
![这里写图片描述][SouthEast 10]

**代码实现：**

public static void insertionSort(int[] arr){
            for(int i = 1;i<=arr.length-1;i++ ){
                // 准备插入的元素temp
                int temp = arr[i];
                // 从i-1依次向后比较
                int j =i-1;
                //大就向后移动
                while(j>=0 &&arr[j]>temp){
                    arr[j+1] = arr[j];
                    j--;
                }
                //小就插入到该元素前面
                arr[j+1] = temp;
            }
        }

注意，在数据近乎有序的时候，插入排序时效率最高的一种排序，它的复杂的近似o(n)。

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

## **选择排序 Selection Sort**  ##

**算法思想：**  
在要排序的一组数中，选出最小的一个数与第1个位置的数交换；然后在剩下的数当中再找最小的与第2个位置的数交换，依次类推。  
![这里写图片描述][SouthEast 11]  
**代码实现：**

public void selectionSort(int[] arr) {
            for (int i = 0; i <= arr.length - 1; i++) {
                int k = i;
                //找出数组中最小的元素
                for (int j = i + 1; j <= arr.length - 1; j++) {
                    if (arr[j] < arr[k]) {
                        k = j;
                    }
                }
                //将最小的元素交换到最前面
                if (k != i) {
                    int temp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = temp;
                }
            }
        }

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

[SouthEast]: /images/20220607/da85d7e26174497896eae33c88d63767.png
[SouthEast 1]: /images/20220607/70260c0c10c64e3ea1485fd50e7fd2bb.png
[SouthEast 2]: /images/20220607/05461290077242d6b9f3a40dc5879738.png
[SouthEast 3]: /images/20220607/3d9e7ca7875b4a8ea8fb3e48e4420b30.png
[SouthEast 4]: /images/20220607/200ba7e111dd4ce2907e098ec1f9e926.png
[SouthEast 5]: /images/20220607/7b55e8a322214ea5a0faadc91b4625b1.png
[SouthEast 6]: /images/20220607/8c66ca54749d4551a4d2cad2592d8eaa.png
[9]: https://www.bilibili.com/video/av10992425/?from=search&seid=11685165048981590259
[SouthEast 7]: /images/20220607/a4d0ee8a55874198955fb36df5bc15ee.png
[SouthEast 8]: /images/20220607/fe64e8f9ad0a400497cb8c7da98fc931.png
[SouthEast 9]: /images/20220607/d7424c8ddbea4bac8ed9362427f3986a.png
[SouthEast 10]: /images/20220607/1424019d77a342cfae27df1cb1b4a6bb.png
[SouthEast 11]: /images/20220607/e5f8a1f980c141ddb09beb3278b5df50.png