数据结构排序算法总结

直接插入排序 + 折半插入排序 + 希尔排序

冒泡排序 + 快速排序

选择排序 + 堆排序

归并排序

1.直接插入排序

前面的有序 后面的无序，无序元素插入到前面的有序列表中

        int len = nums.length, i = 1, j = 0;

        for(i=1; i<len; i++){
            int ele = nums[i];
            
            // 插入过程
            for(j = i-1; j >= 0 && nums[j] > ele; j--)
                nums[j+1] = nums[j];
             
             nums[j+1] = ele;
         }
         return nums;

最坏时间复杂度，最好时间复杂度，空间复杂度，稳定排序

2.折半插入排序：

折半插入排序可以拆分为 折半查找插入位置 + 数组插入

具体折半查找过程 内部的细节总结?折半查找过程-CSDN博客

        int i, j, ele, m, low, high, len = nums.length;
        for (i = 1; i < len; i++)
        {
            ele = nums[i];
            
            // 折半查找
            low = 0; high = i-1;
            while (low <= high)
            {
                m = (low +high) / 2;
                if(nums[m] > ele)
                    high = m-1;
                else
                    low = m+1;
            }
            
            // 排序
            for (j = i-1; j>=low; j--)
                nums[j+1] = nums[j];
            nums[j+1] = ele;
        }

        return nums;

最坏时间复杂度，最好时间复杂度，空间复杂度，稳定排序.

3.冒泡排序：

        // 外层循环控制趟数
        for (int i = 0; i < n - 1; i++) {
            
            flag =false;

            // 内层循环进行比较和交换
            for (int j = 0; j < n - i - 1; j++) {

                if (arr[j] > arr[j + 1]) {

                    swap(arr[j], arr[j+1]);
                    
                    flag = true;
                }
            }
        }

最坏时间复杂度，最好时间复杂度，空间复杂度，稳定排序.

4.快速排序：

    public int partition(int[] nums, int left, int right){
       
        int pivot = nums[left];

        while(left < right){

            while(left < right && pivot <= nums[right]) 
                right--;
            nums[left] = nums[right];

            while(left < right && pivot >= nums[left])
                left++;
            nums[right] = nums[left];

        }

        nums[left] = pivot;
        return left;
    }

    public void quickSort(int[] nums, int left, int right){

        if(left < right){
            int partition = partition(nums, left, right);

            quickSort(nums, left, partition-1);
            quickSort(nums, partition+1, right);
        }

    }

最坏时间复杂度，最好时间复杂度，空间复杂度，不稳定排序.

每一次确定一个点的最终位置，然后把整个数组划分两部分。形成递归树，最坏情况是树高=n，且每一层都要遍历一次数组。 空间复杂度就是整个递归树。

可参考快速排序最好，最坏，平均复杂度分析_对n个记录进行快速排序,在最坏的情况下,其时间复杂度是-CSDN博客

5.选择排序

    public void selectSort(int[] nums){
        for(int i=0; i<nums.length; i++){
            int index = i;
            int min = nums[i];

            
            for(int j=i; j<nums.length; j++){
                index = nums[j] < min ? j:index;
                min = nums[j] < min ? nums[j] : min;
            }

            nums[index] = nums[i];
            nums[i] = min;
        }
    }

最坏时间复杂度，最好时间复杂度，空间复杂度，不稳定排序

6.堆排序

分为建堆，调整，排序。

建堆build_heap:? len/2的位置往前遍历 adjust每一个节点。

    public void buildHeap(int[] nums, int len){
        for(int i=(len)/2; i>0; i--){
            adjust(nums, i, len);
        }
    }

调整adjust： ?for遍历子节点，顶点往下传。

    public void adjust(int[] nums, int k, int len){
        int val = nums[k];
        for(int i=2*k; i<=len; i=i*2){
            if(i+1 <= len && nums[i+1] > nums[i])
                i = i+1;
            if(nums[i] > val){
                nums[k] = nums[i];
                k = i;
            }
            else
                break;
        }
        nums[k] = val;
    }

整合 堆排序 heap_sort

    public void heapSort(int[] nums, int len){
        buildHeap(nums, len);
        for(int i=len; i>1; i--){
            swap(nums,1,i);
            adjust(nums,1,i-1);
        }
    }

最坏时间复杂度，最好时间复杂度，空间复杂度，不稳定排序.

7.归并排序

把两个有序的子数组 合并为一个 大的有序数组。

merge 合并函数

    public void merge(int[] nums, int left, int mid, int right){
        
        int[] arr = new int[right-left+1];
        for(int i=0; i<arr.length; i++){
            arr[i] = nums[left+i];
        }

        int i = 0;
        int j = mid-left+1;
        int k = left;
        while(i <= mid-left && j <= right-left && k <= right){
            if(arr[i] <= arr[j])
                nums[k++] = arr[i++];
            else
                nums[k++] = arr[j++];
        }

        while(i <= mid-left) 
            nums[k++] = arr[i++];
        while(j <= right-left)
            nums[k++] = arr[j++];
    }

递归 拆分数组

    public void mergeSort(int[] nums, int left, int right){
        
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid+1, right);
            merge(nums,left, mid, right);
        }
    }

最坏时间复杂度，最好时间复杂度，空间复杂度，稳定排序.