排序算法(1)

bubble_sort 

比较次数是由数组长度决定，时间会比较长。

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

 selection_sort

注意其中将两个地址上的值交换的swap函数，对不同地址互换赋值很有启发。

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len) {
    int i, j;
    for (i = 0; i < len - 1; i++) {
        int min = i;
        for(j=i+1; j<len; j++)
            if (arr[j] < arr[min]) {
                min = j;
            }
        swap(&arr[min], &arr[i]);
    }
}

insertion_sort

以下这个插入排序的简洁令我意想不到。

首先它成功地在插入这一步做到了最小程度重新赋值数组，另一方面，它利用while的运行条件控制重新赋值的次数。这两点非常重要，也非常巧妙。

key move forwards 是插入排序的本质，同时也体现在了 initialized i = 1。

void insertion_sort(int arr[], int len) {
    int i, j, key;
    for (i = 1; i < len; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {  ///key move forwards
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}