首页  思维导图  详情

十大排序算法

2021-03-31 12:02:31   26  举报





AI智能生成

请大家不要直接克隆，着手梳理一遍才会变成自己的知识

排序算法

作者其他创作

大纲/内容

选择排序

时间复杂度

O(N²)

空间复杂度

O(1)

稳定性

不稳定

7 5 10 10 2 4 2

7 5 10 2 2 4 10

代码实现

public static void sort(int[] nums){
        for (int end = nums.length - 1; end > 0; end--) {
            int maxIndex = 0;
            //start <= end有助于解决一定的不稳定性，但不是完全解决
            for(int start = 1; start <= end ;start++){
                if(nums[start] >= nums[maxIndex]){
                    maxIndex = start;
                }
            }
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[end];
            nums[end] = temp;
        }
    }

冒泡排序

时间复杂度

最坏---逆序

O(N²)

最好---完全有序

O(N)

空间复杂度

O(1)

稳定性

稳定

代码实现

基础版

    public static void sort(int[] nums){
        for (int end = nums.length - 1; end > 0; end--) {
            for(int start = 0; start < end ;start++){
                if(nums[start] > nums[start+1]){
                    int temp = nums[start+1];
                    nums[start+1] = nums[start];
                    nums[start] = temp;
                }
            }
        }
    }

本身就是升序

    public static void sort(int[] nums){
        for (int end = nums.length - 1; end > 0; end--) {
            //判断是否本身就有序的标志
            boolean sorted = true;
            for(int start = 0; start < end ;start++){
                if(nums[start] > nums[start+1]){
                    int temp = nums[start+1];
                    nums[start+1] = nums[start];
                    nums[start] = temp;
                    //一旦出现一次交换，则无序
                    sorted = false;
                }
            }
            //如果没有重排，则数组有序
            if(sorted)break;
        }
    }

尾部局部有序，减少比较次数

    public static void sort(int[] nums){
        for (int end = nums.length - 1; end > 0; end--) {
            //判断是否本身就有序的标志
            boolean sorted = true;
            //如果last=end，数组完全有序，last则不会变化，就会退回基础版
            int last = 1;
            for(int start = 0; start < end ;start++){
                if(nums[start] > nums[start+1]){
                    int temp = nums[start+1];
                    nums[start+1] = nums[start];
                    nums[start] = temp;
                    last = start + 1;
                    //一旦出现一次交换，则无序
                    sorted = false;
                }
            }
            end = last;
            //如果没有重排，则数组有序
            if(sorted)break;
        }
    }

插入排序

时间复杂度

O(N²)

空间复杂度

O(1)

稳定性

稳定

代码实现

    public static void sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i;
            while(j > 0 && temp < arr[j - 1]){
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }

快速排序

时间复杂度

O(nlogn)

空间复杂度

O(logn)

稳定性

稳定

代码实现

public static void sort(int[] arr,int left,int right){
        if(left >= right)return;
        int i = left, j = right;
        //取第一个数作为基数
        int temp = arr[left];
        while(i < j){
            //先从右往左找，填第一个坑
            while (i < j && arr[j] > temp)j--;
            if(i < j)arr[i++] = arr[j];
            while (i < j && arr[i] < temp)i++;
            if(i < j)arr[j--] = arr[i];
        }
        arr[i] = temp;
        sort(arr,left,i-1);
        sort(arr,i+1,right);
    }

归并排序

时间复杂度

O(nlogn)

空间复杂度

O(N)

稳定性

稳定

代码实现

    public static void sort(int[] arr,int left,int right){
        if (left >= right)return;
        int mid = left + (right - left) / 2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        merge(arr,left,mid+1,right);
    }

    public static void merge(int[] arr,int left,int mid,int right){
        int[] temp = new int[right - left + 1];
        int index = 0;
        int i = left;
        int j = mid;
        while(i < mid && j <= right){
            if(arr[i] < arr[j]){
                temp[index++] = arr[i++];
            }else{
                temp[index++] = arr[j++];
            }
        }
        while (i < mid){
            temp[index++] = arr[i++];
        }
        while (j <= right){
            temp[index++] = arr[j++];
        }
        index = 0;
        for (int k = left; k <= right; k++) {
            arr[k] = temp[index++];
        }
    }

堆排序

时间复杂度

O(nlogn)

空间复杂度

O(1)

稳定性

不稳定

代码实现

    public static void sort(int[] arr){
        int len = arr.length;
        //构建大顶堆
        for (int i = (len - 1 ) / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
        for (int i = len - 1; i >= 0 ; i--) {
            System.out.println(arr[0]);
            swap(arr,i,0);
            heapify(arr,0,i);
        }
    }

    public static void heapify(int arr[],int now,int len){
        int left = 2 * now + 1;
        int right = 2 * now + 2;
        int maxIndex = now;
        if(left < len  && arr[left] > arr[maxIndex]){
            maxIndex = left;
        }
        if(right < len  && arr[right] > arr[maxIndex]){
            maxIndex = right;
        }
        if(maxIndex != now){
            swap(arr,maxIndex,now);
            heapify(arr,maxIndex,len);
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

希尔排序

时间复杂度

O(N^1.3)

空间复杂度

O(1)

稳定性

不稳定

代码实现

基础版

    public static void sort(int[] arr){
        //gap是空格间隙
        for(int gap = 4; gap > 0; gap/=2){
            //内部还是插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while(j > gap - 1 && temp < arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

基于Knuth的序列，h = 3h +1

public static void sort(int[] arr){
        int h = 1;
        while(h <= arr.length/3){
            h = h*3 + 1;
        }
        for(int gap = h; gap > 0; gap = (gap-1)/3){
            //内部还是插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                while(j > gap - 1 && temp < arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

桶排序

时间复杂度

O(n+k)

空间复杂度

O(n+k)

稳定性

根据桶内排序算法而定

代码实现

形式不固定

基数排序

时间复杂度

O(n*k)

空间复杂度

O(n*k)

稳定性

稳定

代码实现

public static void sort(int[] arr){
        //求最高位数
        int max = 0;
        int min = 0;
        for (int i : arr) {
            if (i > max)max = i;
            if (i < min)min = i;
        }
        int digit = 1;
        while(max / 10 > 0){
            max /= 10;
            digit++;
        }
        //开始基数排序
        for (int i = 1; i <= digit; i++) {
            int[] count = new int[10];
            int[] result = new int[arr.length];
            //求每次该和多少取余
            int times = 1;
            for(int j = 1;j < i; j++){
                times *= 10;
            }
            for (int k = 0; k < arr.length; k++) {
                count[(arr[k]/times)%10]++;
            }
            for (int l = 1; l < count.length; l++) {
                count[l] += count[l-1];
            }
            for (int m = arr.length - 1; m >= 0 ; m--) {
                result[--count[(arr[m]/times)%10]] = arr[m];
            }
            System.arraycopy(result,0,arr,0,arr.length);
        }
    }

计数排序

时间复杂度

O(n+k)

空间复杂度

O(n+k)

稳定性

稳定

代码实现

不稳定

public static void sort(int[] arr,int low,int high){
        int[] count = new int[high - low + 1];
        int[] result = new int[arr.length];
        for (int i : arr) {
            count[i]++;
        }
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < count.length; j++) {
                while (count[j]-- > 0){
                    result[i++] = j;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result[i];
        }
    }

改进成稳定

public static void sort(int[] arr,int low,int high){
        int[] count = new int[high - low + 1];
        int[] result = new int[arr.length];
        for (int i : arr) {
            count[i - low]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            result[--count[arr[i] - low]] = arr[i];
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result[i];
        }
    }