排序算法总结

1.冒泡排序

基本思想：两数比较大小，较大数后移，较小数前移
平均时间复杂度：o(n2)
代码实现：

void bubblesort(int arr[],int len) {
    int temp, i, j;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

针对问题：顺序排好后，冒泡排序可能会继续下一轮循环，直到满足退出条件
优化方案：若本轮没有发生两数交换，则退出循环

void bubblesort(int arr[],int len) {
    int temp, i, j,flag;
    for (i = 0; i < len - 1; i++) {
        flag = 0
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = 1;/*发生两数交换，flag 置为 1*/
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}

2.选择排序

基本思想：第 i 次遍历数组，找出最小的数值与第 i 个元素交换
平均时间复杂度：o(n2)
代码实现：

void sort(int a[],int n){
    int i,j,min,t;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++){
            if(a[j]<a[min]){
                min=j;
            }
        }
        if(min!=i){
            t=a[i];
            a[i]=a[min];
            a[min]=t;
        }
    }
}

参考资料：