算法--排序1

浏览数：23 / 时间：2015年06月08日

算法–排序1

约定：在代码中l，和r都是闭区间，例如，有10个元素的数组，那么我的代码中l和r分别是0和9。（使用的是从小到大排序）

冒泡排序
假如有n个元素，那我们要走n-1次，选择出一个最大，然后丢到后面去。

void bubble(int l, int r) {
     for(int i = l; i <= r-1; i++) {      // n - 1次
        for(int j = l; j < r-i; j++) {    // 因为r-i后面的值都是已经被丢过（排好序）
            if(a[j] > a[j+1]) {
                swap(a, j, j+1);          // 发现大的就开始往后面丢
            }
        }
    }
}

选择排序
和冒泡排序不同的是，选择排序一开是先先选择出最小的，然后开始放到前面。我们要找出一个数组中的最小值。

int min = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] > min) {
        min = a[i];
    }
}

现在我们只需要找到最小值的下标。

int min = 0;
for (int i = 1; i < n; i++) {
    if (a[i] > a[min]) {
        min = i;
    }
}

下面就是选择排序的代码。

void select_sort(int l, int r) {
    for (int i = l; i <= r-1; ++i) {
        int min = i;
        for (int j = i+1; j <= r; ++j) {
            if (a[j] < a[k]) {
                min = j;
            }
        }
        swap(a, k, i);
    }
}

插入排序
插入排序就好像是我们玩扑克牌时候的排序，我们摸到一张牌，那我们就要从右边开始往左边插，（这里假设你是用左手拿着一堆牌，如果你是右手那反过来）。

首先，假设这张牌的大小为key且他的下标是i，那么他要从i-1比到0。j从i-1到0。如果有比他大的牌，把这张牌的向后推，从j推向（j+1）。如果这张牌（j）小于key，那我们key的牌就要放在j的后面，也就是j+1 = key。

void insert_sort(int l, int r) {
    for(int i = l+1; i <= r; i++) {
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}