排序算法

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

目前包括：选择排序，插入排序，归并排序

情景：将数组 a 中的 nn 个整数从小到大排序

1
2
3
4
5
6
int[] a;
void swap(int[] a, int i, int j) {
    int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
}

选择排序

比较次数：n(n−1)2\frac{n(n-1)}{2}

时间复杂度：O(n2)O(n^2)

选择最小

1
2
3
4
5
6
7
for (int i=0;i<a.length-1;i++) {
    int minIndex = i;
    for (int j=i+1;j<a.length;j++)
        if (a[j] < a[minIndex])
            minIndex = j;
    swap(a, minIndex, i);
}

选择最大

1
2
3
4
5
6
7
for (int i=0;i<a.length-1;i++) {
    int maxIndex = i;
    for (int j=0;j<a.length-i;j++)
        if (a[j] > a[maxIndex])
            maxIndex = j;
    swap(a, maxIndex, i);
}

插入排序

时间复杂度：O(n2)O(n^2)

1
2
3
4
5
6
for (int i=1;i<a.length;i++) {
    int cur = a[i], newIdx = i;
    while (newIdx > 0 && a[newIdx-1] > cur)
        a[newIdx] = a[--newIdx];
    a[newIdx] = cur;
}

归并排序

时间复杂度：O(nlog⁡n)O(n\log{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
void mergeSort(int[] a) {
    mergeSort(a, 0, a.length-1);
}
void mergeSort(int[] a, int start, int end) {
    if (start >= end) return;
    
    int mid = (start+end)/2,
          i = start,
          j = mid+1,
        len = end-start+1,
     temp[] = new int[len];

    mergeSort(a, i, mid);
    mergeSort(a, j, end);

    for (int k=0;k<len;k++)
        if (j>end || i<=mid && a[i]<a[j])
            temp[k] = a[i++];
        else
            temp[k] = a[j++];

    for (int k=0;k<len;k++)
        a[start+k] = temp[k];
}