[数据结构与算法]排序算法（一）

选择排序

• 算法思想：如果有N个元素需要排序，那么首先从N个元素中找到最小的那个（称为第0小的）放在第0个位子上（和原来的第0个位子上的元素交换位置），然后再从剩下的N-1个元素中找到最小的放在第1个位子上，然后再从剩下的N-2个元素中找到最小的放在第2个位子上…直到所有元素都就为。

//代码
#include <iostream>
using namespace std;
void SelectSort(int a[], int size) {
    for (int i = 0; i < size - 1; i++) { //每次循环将第i小的元素放好
        int tmpmin = i;//用来记录从第i个到第size-1个元素中，最小的那个元素的下标
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[tmpmin]) tmpmin = j;
        }
        //下面将第i小的元素放在第i个位子上，并将原来占着第i个位子上的元素挪到后面
        int tmp = a[i];
        a[i] = a[tmpmin];
        a[tmpmin] = tmp;
    }
}
int main() {
    int a[] = {1, 5, 3, 2};
    SelectSort(a, 4);
    for (int i = 0; i < 4; i++) {
        cout << a[i];
    }
    return 0;
}
//算法效率O(n^2)

插入排序

• 算法思想：将整个数组a分为有序的部分和无序的两个部分，前者在左边，后者在右边，开始有序的部分只有a[0],其余都属于无序的部分。每次取出无序部分的第一个(最左边)元素，把它加入到有序部分。假设插入到合适位置p，则原p位置及其后面的有序部分元素，都向右移动一个位子。有序的部分即增加了一个元素。直到无序的部分没有元素

//代码
#include <iostream>
using namespace std;
void InsertSort(int a[], int size) {
    for (int i = 1; i < size; i++) {
    //a[i]是最左的无序元素，每次循环将a[i]放到合适位置
        for (int j = 0; j < i; j++) {
            if (a[j] > a[i]) {
            //要把a[i]放到位置j，原下标j到i-1的元素都往后移一个位子
                int tmp = a[i];
                for (int k = i; k > j; k--) {
                    a[k] = a[k - 1];
                }
                a[j] = tmp;
                break;
            }
        }
    }
}
int main() {
    int a[] = {1, 3, 2, 0};
    InsertSort(a, 4);
    for (int i = 0; i < 4; i++) {
        cout << a[i];
    }
    return 0;
}
//算法效率O(n^2)

冒泡排序

• 算法思想：将整个数组a分为有序的部分和无序的两个部分。前者在右，后者在左边。开始，整个数组都是无序的。有序的部分没有元素。每次要使得无需部分最大的元素移动到有序部分第一个元素的左边。移动方法是：依次比较相邻的两个元素，如果前面的比后面的大，就交换他们的位置。这样，大的元素就像水里的气泡一样不断往上浮。移动结束有序部分增加一个元素。直到无序的部分没有元素。

//代码
#include <iostream>
using namespace std;
void BubbleSort(int a[], int size) {
    for (int i = size - 1; i > 0; i--) {
    //每次要将未排序的最大值移动到下标i的位置
        for (int j = 0; j < i; j++) {
        //依次比较相邻两个元素
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}
int main() {
    int a[] = {1, 3, 2, 0};
    BubbleSort(a, 4);
    for (int i = 0; i < 4; i++) {
        cout << a[i];
    }
    return 0;
}
//算法效率O(n^2)