排序算法总结

Cutewr大约 4 分钟

排序算法总结

总结

选择排序

每次找到剩下序列中最小的，交换最小的和最开始的位置

【不稳定算法】如果当前数A后面的序列中，先出现了一个相等的数A2，又出现了一个比它小的数B，就会交换A和B，这样就破坏了A和A2的稳定性。

最好最坏都一样，什么数据都是O(n²)

时间复杂度：O(n²)

public static void selectSort(int []nums){
    for(int i=0;i<nums.length-1;i++){ //比较轮数
        int min=i;
        for(int j=i+1;j<nums.length;j++){	//j从i+1到最后一位，找出最小值
            if (nums[j]<nums[min]) {
                min=j;
            }
        }
        if (i!=min) {
            int temp=nums[min];
            nums[min]=nums[i];
            nums[i]=temp;   
        }
    }
}

冒泡排序

算法流程：每次从左往右比，两两交换，把最大的冒到右边。

【稳定算法】遇到等于的，不会交换

最好情况：已经正序排序；最坏情况：倒序排序

时间复杂度：O(n²)

public static void bubbleSort(int []nums){
    for(int i=1;i<nums.length;i++){   //排序次数
        boolean flag=true;  //如果前面的数都比后面的数小，那就排序完成了
        for(int j=0;j<nums.length-i;j++){
            if (nums[j]>nums[j+1]) {
                int temp=nums[j];
                nums[j]=nums[j+1];
                nums[j+1]=temp;
                flag=false;
            }
        }
        if (flag) {
            break;
        }
    }
}

插入排序

对于基本有序的数组最好用，稳定。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

从第二个数开始把后面的数插到前面已经排好序的数组中

public static void insertSort(int []nums){
    for (int i=1;i<nums.length;i++){
        for (int j=i;j>0;j--){
            if (nums[j]<nums[j-1]){
                int temp=nums[j];
                nums[j]=nums[j-1];
                nums[j-1]=temp;
            }else{
                break;
            }
        }
    }
}

希尔排序

希尔排序是在选择排序上的改进

首先按照间隔为4，对数组进行排序，再逐渐减少间隔为1。提高插入排序的效率。

是不稳定的，因为它是分间隔插入比较的，相同的在后面的元素可能被插入到前面来。

public static void shellSort(int []nums){
    for (int gap=4;gap>0;gap/=2){
        for (int i=gap;i<nums.length;i++){
            for (int j=i;j>gap;j-=gap){
                if (nums[j]<nums[j-gap]){
                    int temp=nums[j];
                    nums[j]=nums[j-gap];
                    nums[j-gap]=temp;
                }else{
                    break;
                }
            }
        }
    }
}

归并排序

思想：合并两个有序数组，则得到是一个大的有序数组。稳定的。

时间复杂度:O(nlogn)；空间复杂度:On

递归调用归并排序，从递归底层，先两两合并，再把合并完的数组进行合并。

如果我们要对对象进行排序，需要排序是稳定的，使用归并排序。

TimSort中既用到了归并排序，又用到了二分插入排序。

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

快速排序

把pivot放到它该在的位置，并且递归排序左右两侧。

时间复杂度：O(nlogn)【很稳定】

最差的情况：正序or逆序排序，这样每次pivot都是最边上那个值。每次只能确定一个位置的值。

时间复杂度：O(nlogn)

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int []nums={2, 3, 1, 4, 5, 0};
        Arrays.sort(nums);
        quickSort(nums,0,nums.length-1);
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    public static void quickSort(int []nums,int left,int right){
        if (left>=right) return;
        int pivot=findPivot(nums,left,right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    public static int findPivot(int []nums,int left,int right){
        int flag=nums[right];
        int rightBound=right;
        right--;
        while (left<=right){
            while (left<=right&&nums[left]<=flag) left++;
            while (left<=right&&nums[right]>flag) right--;
            if (left<right) swap(nums,left,right);
        }
        int temp=nums[rightBound];
        nums[rightBound]=nums[left];
        nums[left]=temp;
        return left;
    }

    public static void swap(int []nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
}

以下三种不是比较排序，是桶排序

计数排序

算法思想

量大但是取值范围小
大型企业按照员工年龄排序【18~65】
如何快速知道高考名次【0~750 但是高考人数非常多几十上百万】

使用一个计数数组，统计每个值出现了多少次。