排序算法

发表于 分类于 本文字数： 426 阅读时长 ≈ 2 分钟

各类排序算法及比较

选择排序:

每次选择还未排序的值中最小的一个, 和第一个交换.

思路很清晰, 代码很好写, 时间复杂度为O(n^2).

伪代码:

1
2
3
4
5
6
7
8
9
// 要排序的数组: data[n]
循环i从0到n-1:
    min = 0x7fffffff
    pos = 0
    循环j从i到n-1:
        如果 min > data[j]:
            pos = j
            min = data[j]
    交换data[pos]与data[i]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int i,j,min,pos,t;
for(i = 0; i < n; ++ i){
    min = 0x7fffffff;
    pos = 0;
    for(j = i; j < n; ++ j){
        if(min > data[j]){
            pos = j;
            min = data[j];
        }
    }
    t = data[i];
    data[i] = data[pos];
    data[pos] = t;
}

冒泡排序

枚举相邻的两个, 如果前者大于后者, 交换.

经过每一轮比较, 最大的一个一定会跑到数组最后面, 就像气泡浮出水面的过程, 因此叫做冒泡排序.

思路简单, 代码好写, 时间复杂度O(n^2).

伪代码:

1
2
3
4
5
// 要排序的数组: data[n]
循环i从0到n-2:
    循环j从0到n-i-2:
        如果 data[j] > data[j+1]:
            交换data[j], data[j+1];

代码1:

1
2
3
4
5
6
7
8
9
10
int i,j,t;
for(i = 0; i < n-1; ++ i){
    for(j = 0; j < n-i-1; ++ j){
        if(data[j] > data[j+1]){
            t = data[j];
            data[j] = data[j+1];
            data[j+1] = t;
        }
    }
}

代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sorted = 0;
int t = 0;
while( !sorted ){ //当还没排序好
    sorted = 1; //先认为已经排序好
    for( int i = 1; i < n; ++ i ){
        if( data[i - 1] > data[i] ){
            t = data[i - 1];
            data[i - 1] = data[i];
            data[i] = t;
            sorted = false;// 还没排序完毕
        }
    }
    n--; // 最后一位已经排序好, 可以不用管它了
}

借助标志位sorted, 能使得程序在已经排序完毕之后提前退出.