排序算法

发表于 | 分类于
字数统计: 635 | 阅读时长 ≈ 2
回顾基本的排序算法

排序算法

基本（做到快速无bug写出）

  • 冒泡排序
  • 插入排序

常考

  • 归并排序
  • 快速排序
  • 拓扑排序

其他（开拓思路）

  • 堆排序
  • 桶排序

冒泡排序

空间复杂度:O(1)

时间复杂度:O(n^2)

稳定

插入排序

空间复杂度:O(1)

时间复杂度:O(n^2)

稳定

归并排序

核心思想：分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 升序排列int数组
 * @param A:需要排列的数组
 * @param lo:数组起始下标
 * @param hi:数组结束下标
 */
public static void mergeSort(int[] A, int lo, int hi){
        //升序方式排列数组
        //如果lo>=hi,说明数组中只有一个元素，应该返回
        if(lo >= hi) return;
        //取中位数
        int mid = lo + (hi-lo)/2;

        //左右递归两遍的数组
        mergeSort(A, lo, mid);
        mergeSort(A, mid+1, hi);

        //递归结束,进行合并
        merge(A, lo, mid, hi);
    }

    private static void merge(int[] nums, int lo, int mid, int hi){
        //复制原来的数组
        int[] cp = nums.clone();

        //k表示从什么位置修改原来的数组,i是左边开始的起始位置,j是右边开始的起始位置
        int k = lo, i = lo, j = mid+1;
        while (k <= hi){
            //如果左边已经放置完了,就直接放置右边剩下的
            //如果右边已经放置完了,就直接放置左边剩下的
            //如果左边大于右边,则放置右边,否则放置左边.
            if(i > mid) nums[k++] = cp[j++];
            else if(j > hi) nums[k++] = cp[i++];
            else if(cp[i] > cp[j]) nums[k++] = cp[j++];
            else nums[k++] = cp[i++];
        }
    }

时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 升序排列int数组
 * @param nums:需要排列的数组
 * @param lo:数组起始下标
 * @param hi:数组结束下标
 */
public static void quickSort(int[] nums, int lo, int hi){
    //如果只有一个元素了,则返回
    if(lo >= hi) return ;

    //获取参照值
    int p = partition(nums, lo, hi);

    //把比p小的放到左边,比p大的放到右边
    quickSort(nums, lo, p-1);
    quickSort(nums, p+1, hi);
}

private static int partition(int[] nums, int lo, int hi){
    int tmp = nums[lo];

    while (lo < hi){
        while (lo < hi && nums[hi] > tmp) hi--;
        nums[lo] = nums[hi];
        while (lo < hi && nums[lo] < tmp) lo++;
        nums[hi] = nums[lo];
    }
    nums[lo] = tmp;
    return lo;  //返回中轴位置
}

时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定

0%