五大排序code总结

上周梳理了冒泡、选择、插入、归并、快排五大排序的思路与代码然后自己又手写了一遍。发现还是有很多细节上的问题在这里针对代码梳理下。

1. 冒泡排序

冒泡排序是一个双层嵌套循环然后在内层循环swap相邻元素的过程

2. 选择排序

选择排序是一个双层嵌套循环每一次遍历找出max的位置并在内层循环结束后swap

i 和 max位置的过程

3. 插入排序

插入排序是将队列第二个元素及以后元素一个个找到对应位置的过程

第一层循环从i=1开始遍历j = i-1key = arr[i]。

如果arr[j] < key就a[j+1] = a[j]。这句话的含义是j+1的位置其实就是key的位置将这个位置的值替换为a[j]。

然后检查之前的值是否都比这个小如果不是就再替换掉以此类推所以代码是下面这样

在这里要注意和快排的 区别快排代码如下

插入的元素更新是在循环内快排是在循环外。

一次遍历检查完j的位置值还没更新又因为在上面操作中j被减一所以有

4. 归并排序

归并和快排都是递归的思想。

并且主函数结构都类似

上述细微的差别的原因是

归并是先分再治先分成一个个元素分完再排序快排是每次先找到基准值所在的位置然后根据基准值划分出左右两部分再进行递归操作。

merge函数这里只需要理解在第一次while循环时有一端到头就结束在第二次循环时将未结束的那一端复制到临时数组在第三次循环时将临时数组复制到原数组

5. 快排

快排有两层循环第一层循环条件是start < end这是为了当两个元素相遇时才意味着遍历完所有元素内层循环是每次都要找到与key相比需要更新值的元素

注意更新元素值的写法a[j] = a[i]。

另外两点在插入排序和归并排序中已经说过不再赘述。五种代码如下

#include <iostream>
using namespace std;

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

void selection_sort(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        int max = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[max] < arr[j]) {
                max = j;
            }
        }
        swap(arr[max], arr[i]);
    }
}

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

void merge(int arr[], int start, int end, int arrf[]) {
    int mid = start + (end - start) / 2;
    int i = start;
    int j = mid;
    int t = 0;
    while (i < mid && j < end) {
         if (i < j && arr[i] < arr[j]) {
            arrf[t++] = arr[i++];
        } else 
        {
            arrf[t++] = arr[j++];
        }
    }
    while (i < mid)
    {
        arrf[t++] = arr[i++];
    }
    while (j < end)
    {
        arrf[t++] = arr[j++];
        
    }
    t = 0;
    while (start < end) {
        cout << "arrf = " << arrf[t] << endl;
        arr[start++] = arrf[t++];
    }
}

void merge_sort(int arr[], int start, int end, int arrf[]) {
    int mid = start + (end - start) / 2;
    if (start < end) {
        merge_sort(arr, start, mid, arrf);
        merge_sort(arr, mid + 1, end, arrf);
        merge(arr, start, end, arrf);
    }
}

int quick_sort_1(int arr[], int start, int end) {
    int i = end;
    int j = start;
    int key = arr[start];
    while (j < i) {
        while (i > j && arr[i] >= key) {
            --i;
        }
        arr[j] = arr[i];
        while (i > j && arr[j] <= key) {
            ++j;
        }         
        arr[i] = arr[j];
    }
    arr[i] = key;
    return i;
}

void quick_sort(int arr[], int start, int end) {
    if (start < end) {
        int mid = quick_sort_1(arr, start, end);
        quick_sort(arr, start, mid - 1);
        quick_sort(arr, mid + 1, end);
    }
}

int main() {
    int arr[] = {47, 35, 12, 82, 8, 33, 45, 47};
    int arrf[8];
    quick_sort(arr, 0, 7);
    for (int k = 0; k < 8; k++) {
        cout << arr[k] << endl;
    }
}