数组排序——N种方法小结

C的各种排序算法(GCC编译）:

 

排序和查找都是数据结构里，很重要的组成部分。对一个算法的综合评价是时间复杂度和空间复杂度。一般情况下，我们用时间复杂度来衡量一个算法的优劣。其实算法都有其适合的场合。不能一概而论。数组下标从0开始，在C中。

1.冒泡法：相邻的俩个元素进行比较交换，下面是按照从小到大顺序排列的。
#include
void bubblesort(int *pa, int cnt){
    int temp,i,j;
    for (i = 0;i < cnt -1;i ++){//只要进行cnt-1次就可以排序完毕了。每次把一个最大的沉底
      for (j=0;j < cnt - 1 -i;j++){//因为后面用的是i+1，所以可以比较到底
         if(pa[i] > pa[i+1]){ //用的同一个参数i进行比较，类似冒泡
            temp = pa[i];
            pa[i] = pa[i+1]
            pa[i+1] = temp;
         }
      }  
   }
}
int main() {
  int i;
  int c[] = {9,8,7,6,5};
  bubblesort(c,5);   //函数调用，数组名就是指向该数组的指针
  for (i = 0; i < 5; i++ ){
    printf("c[%d] = %d “，i,c[i]);
  }
  return 0；
}最糟情况是数字本身给的是倒序，那么需要进行n*(n-1)/2次循环。时间复杂度为O(n)=n*n;交换的次序跟数组本身有很大的关系。

2.交换法：从小到大。用第0个元素和后面的元素依次比较，如果小于，那么交换。
void exchangesort(int *pa, int cnt) {
    int temp,i,j;
    for(i = 0;i < cnt -1;i++) {
        for(j=i+1;j < cnt;j++) {
            if(pa[j] < pa[i]) {
                temp = pa[i];
                pa[i] = pa[j];
                pa[j] = temp;   
            }
        }
    }
}最多进行n*（n-1）/2次循环，就可以全部比较过，然后可以确保完整排序。效率跟上面的差不多。

3.选择法：