Skip to content

13_排序.md

Latest commit

 

History

History
226 lines (169 loc) · 5.2 KB

13_排序.md

File metadata and controls

226 lines (169 loc) · 5.2 KB
Raw

排序

1、常见的简单排序算法

I. 选择排序

选择排序思路：选择出数组中的最小元素，将它与数组的第一个元素交换位置。 再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。 不断进行这样的操作，直到将整个数组排序。

public void sort(int[] arr){
    int N = arr.length;
    int minIndex = -1;
    for(int i=0;i<N;i++){ // arr[i] 是当前元素
        minIndex=i;
        for(int j=i+1;j<N;j++){ //arr[j] 当前元素后面的元素
            if(arr[j]<arr[minIndex]){
                minIndex=j;
            }
        }
        if(minIndex==i){ //TODO:这里有个小优化：如果当前元素是最小的则不用交换了
            continue;
        }
        swap(arr,minIndex,i);
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

@Test
public void test(){
    int[] a={3,5,2,4,1,0,-3};
    PrintArr.printArray(a);
    sort(a);
    PrintArr.printArray(a);
}

选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

II. 冒泡排序

冒泡排序思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。

public void sort(int[] arr){
    for(int i=arr.length-1;i>0;i--){
        for(int j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr,j,j+1);
            }
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

@Test
public void test(){
    int[] a={3,5,2,4,1,0,-3};
    PrintArr.printArray(a);
    sort(a);
    PrintArr.printArray(a);
}

添加一个状态变量对冒泡排序进行优化：

public void sort(int[] arr){
    boolean isSorted = false;
    for(int i=arr.length-1;i>0 && !isSorted ;i--){
        //!isSorted 条件，当 isSorted=true 时说明是有序的，则不需要再执行了
        isSorted = true; //初始时认为是有序的
        for(int j=0;j<i;j++){
            if(arr[j]>arr[j+1]){
                isSorted = false; //存在逆序，则是无序的
                swap(arr,j,j+1);
            }
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

@Test
public void test(){
    int[] a={3,5,2,4,1,0,-3};
    PrintArr.printArray(a);
    sort(a);
    PrintArr.printArray(a);
}

冒泡排序是稳定的排序算法，平均时间复杂度是 O(n^2)。

III、插入排序

插入排序思路：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}， 它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)， 插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。

public void sort(int[] arr){
    for(int i=1;i<arr.length;i++){ //默认 arr[0] 已经有序
        //a[0,,,i] 已经有序，加入一个元素后，进行一次冒泡(从后向前的)，就必然是有序的了。
        for(int j=i;j>0 && arr[j-1]>arr[j];j--){
            swap(arr,j-1,j);
        }
    }
}

private void swap(int[] arr,int i,int j){
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

IV、希尔排序



2、常见的高级排序算法


I、归并排序




II、快速排序




3、堆排序


4、最小的 k 个数（44）


最小的 k 个数


public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer> res = new ArrayList<>();
    if(k<=0 || k>input.length){
        return res;
    }
    int index = findKthSmallest(input,k-1);
    if(index==-1){
        return res;
    }

    for(int i=0;i<=index;i++){
        res.add(input[i]);
    }
    return res;
}

//查找数组中第 k 小的元素
private int findKthSmallest(int[] input,int k){
    int l=0,r=input.length-1;
    while (l<=r){
        int p = partion(input,l,r);
        if(p==k){
            return p;
        }else if(p<k){
            l = p+1;
        }else{
            assert p>k;
            r = p-1;
        }
    }
    return -1;
}

//使用快速排序中的切分思路
private int partion(int[] nums,int start,int end){
    int pivot = nums[start];

    while (start<end){
        while (start<end && nums[end]>=pivot){
            end--;
        }
        nums[start]=nums[end];
        while(start<end && nums[start]<=pivot){
            start++;
        }
        nums[end]=nums[start];
    }
    nums[start] = pivot;
    return start;
}