几大排序算法简单介绍及其代码实现

一、选择排序

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。进行的操作次数 n*(n-1)/2

int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    for (int i = 0; i < arr.size() - 1; i++) {
        int minn = arr[i],index=i;
        for (int j = i+1; j < arr.size(); j++) {
            if (arr[j] < minn) {
                minn = arr[j];
                index = j;
            }
        }
        arr[index] = arr[i];
        arr[i] = minn;
    }
    for (int i = 0; i < arr.size(); i++) cout << arr[i];
    return 0;
}

二、冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。需要最多的操作次数 n*(n-1)/2

int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    for (int i = arr.size()-1; i>0; i--) {
        int flag = 0;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                //用异或进行元素交换
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j+1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
                flag = 1;
            }
        }
                 //在一轮循环中没有进行元素交换，说明当前数组已经有序
        if (flag == 0) break;
    }
    for (int i = 0; i < arr.size(); i++) cout << arr[i];
    return 0;
}

三、插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。最坏的情况是数组是倒序的，需要进行 n(n-1)/2次比较和 n(n-1)/2次交换，最好的情况是数组已经是有序的，需要进行n-1次比较和0次交换。插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    for (int i = 1; i < arr.size(); i++) {
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            arr[j] = arr[j] ^ arr[j + 1];
            arr[j+1] = arr[j] ^ arr[j + 1];
            arr[j] = arr[j] ^ arr[j + 1];
        }
    }
    for (int i = 0; i < arr.size(); i++) cout << arr[i];
    return 0;
}

四、希尔排序

插入排序每次只能交换相邻的逆序元素，对于大规模的数组，排序很慢。希尔排序则是通过交换不相邻的元素，每次可以将逆序数量减少大于 1，加快了排序速度。

int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    int h = arr.size() / 2;//需要设置希尔常量
    while (h) {
        for (int i = h; i < arr.size(); i++) {
            for (int j = i - h; j >= 0 && arr[j] > arr[j + h]; j -= h) {
                arr[j] = arr[j] ^ arr[j + h];
                arr[j+h] = arr[j] ^ arr[j + h];
                arr[j] = arr[j] ^ arr[j + h];
            }
        }
        h /= 2;
    }
    for (int i = 0; i < arr.size(); i++) cout << arr[i];
    return 0;
}

五、归并排序

将待排序的数组不断地分成两部分，对不同部分的元素分别进行排序，然后归并起来。（空间复杂度为什么是n）

vector<int> merge(vector<int>&a, vector<int>&b) {
    if (a.empty()) return b;
    else if (b.empty()) return a;
    else {
        vector<int> res;
        int a1 = a.size(), b1 = b.size(), i = 0, j = 0;
        while (i < a1&&j < b1) {
            if (a[i] < b[j]) {
                res.push_back(a[i]);
                i++;
            }
            else {
                res.push_back(b[j]);
                j++;
            }
        }
        while (i < a1) {
            res.push_back(a[i]); i++;
        }
        while (j < b1) {
            res.push_back(b[j]); j++;
        }
        return res;

    }
}
vector<int> fun(vector<int> &array, int l, int r) {

    if (l > r) {
        vector<int> t = {};
        return t;
    }
    if (l == r) {
        vector<int> t;
        t.push_back(array[l]);
        return t;
    }
    else {
        vector<int> left = fun(array, l, (l + r) / 2);
        vector<int> right = fun(array, (l + r) / 2 + 1, r);
        return merge(left,right);

    }
}
int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    int l = 0, r = arr.size() - 1;
    vector<int> res = fun(arr, l, r);
    for (int i = 0; i < res.size(); i++) cout << res[i];
    return 0;
}

六、快速排序

首先从待排序的数组中选择一个元素作为比较的基准，然后遍历一遍数组，将所有比这个值小的元素放到左边，比这个值大的元素放到右边，最后分别对左边和右边的元素重复上述过程，直到所有元素都排好序

void quickSort(vector<int>&a, int low, int high)
{
    if (low < high)  //判断是否满足排序条件，递归的终止条件
    {
        int i = low, j = high;   //把待排序数组元素的第一个和最后一个下标分别赋值给i,j，使用i,j进行排序；
        int x = a[low];    //将待排序数组的第一个元素作为哨兵，将数组划分为大于哨兵以及小于哨兵的两部分                                   
        while (i < j)
        {
            while (i < j && a[j] >= x) j--;  //从最右侧元素开始，如果比哨兵大，那么它的位置就正确，然后判断前一个元素，直到不满足条件
            if (i < j) a[i++] = a[j];   //把不满足位次条件的那个元素值赋值给第一个元素，（也即是哨兵元素，此时哨兵已经保存在x中，不会丢失）并把i的加1
            while (i < j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小，比其小，那么它所处的位置就正确，然后判断后一个，直到不满足条件
            if (i < j) a[j--] = a[i];  //把不满足位次条件的那个元素值赋值给下标为j的元素，（下标为j的元素已经保存到前面，不会丢失）并把j的加1
        }
        a[i] = x;   //完成一次排序，把哨兵赋值到下标为i的位置，即前面的都比它小，后面的都比它大
        quickSort(a, low, i - 1);  //递归进行哨兵前后两部分元素排序 ， low,high的值不发生变化，i处于中间
        quickSort(a, i + 1, high);
    }
}
int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    int l = 0, r = arr.size() - 1;
    quickSort(arr, l, r);
    for (int i = 0; i < arr.size(); i++) cout << arr[i];
    return 0;
}

七、堆排序

首先将待排序序列构造成一个大根堆，将根节点与末尾元素交换，此时末尾就为最大值，然后将剩下的前n-1个元素重新构造大根堆，并将该根节点与倒数第二个数交换得到第二大的数字，如此反复循环，最终得到一个有序序列。

void adjuct(vector<int>&arr, int i,int len) {
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    //找出当前节点与它的左右孩子节点中值最大的节点
    int index = i, maxval = arr[i];
    if (l<len && arr[l]>maxval) { maxval = arr[l]; index = l; }
    if (r<len && arr[r]>maxval) { maxval = arr[r]; index = r; }
    if (index != i) {
        //调整节点并递归
        arr[index] = arr[i];
        arr[i] = maxval;
        adjuct(arr, index,len);
    }
}
int main() {
    vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
    //1.建堆，自下而上
    int len = arr.size();
    for (int i = len / 2 - 1; i >= 0; i--) adjuct(arr, i,len);
    //2.排序
    for (int i = len - 1; i > 0; i--) {
        int tmp = arr[i];
        arr[i] = arr[0];
        arr[0] = tmp;
        adjuct(arr, 0, i);
    }