文章目录

• 1、直接插入排序
• 2、希尔排序(缩小增量排序)
• 3、冒泡排序
• 4、快速排序
• 5、简单选择排序
• 6、堆排序
• 7、归并排序
• 8、基数排序

1、直接插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。
时间复杂度： O ( n 2 ) O(n^2) O(n2)

void insertSort(vector<int>& array) {
    for (int i = 1; i < array.size(); i++) {
        if (array[i] < array[i - 1]) {
            int temp = array[i];
            int index = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (array[j] > temp) {
                    array[j + 1] = array[j];
                } else {
                    index = j + 1;
                    break;
                }
            }
            array[index] = temp;
        }
    }
}

2、希尔排序(缩小增量排序)

基本思想：先将待排序表分割成若干形如[i, i+d, i+2d, ‘’’, i+kd]的特殊子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。
时间复杂度： O ( n 2 ) O(n^2) O(n2)

void shellSort(vector<int>& array) {
    for (int i = array.size()/2; i>=1; i/=2) {
        for (int j = i; j < array.size(); j++) {
            if (array[j] < array[j - i]) {
                int temp = array[j];
                int index = j % i;
                for (int k = j - i; k >= 0; k-=i) {
                    if (array[k] > temp) {
                        array[k + i] = array[k];
                    } else {
                        index = k + i;
                        break;
                    }
                }
                array[index] = temp;
            }
        }
    }
}

3、冒泡排序

基本思想：从前往后（或从后往前）两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。
时间复杂度： O ( n 2 ) O(n^2) O(n2)

void bubbleSort(vector<int>& array) {
    for (int i = 0; i < array.size(); i++) {
        bool flag = false;
        for (int j = 0; j < array.size() - 1 - i; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                flag = true;
            }
        }
        if (!flag) {
            return;
        }
    }
}

4、快速排序

基本思想：快速排序基本思想是基于分治法的，在待排序表L[0…n-1]中任取一个元素pivot作为枢轴，通过一趟排序将表划分为两部分L[0…k-1]和L[k…n-1]，使得L[0…k-1]中的元素都小于等于pivot，L[k…n-1]中的元素都大于等于pivot，最后将pivot放在其最终位置L(k)上，这个过程称为一次划分，然后分别对两个子表重复上述过程，直至每部分只有一个元素或者为空为止，此时所有元素都放在了其最终位置上。
时间复杂度： O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

int partition(vector<int>& array, int low, int high) {
    int pivot = array[low];
    while (low < high) {
        while (low < high && array[high] >= pivot) {
            high--;
        }
        array[low] = array[high];
        while (low < high && array[low] <= pivot) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = pivot;
    return low;
}

void quickSort(vector<int>& array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }
}

5、简单选择排序

基本思想：每一趟（如第i趟）在待排序元素中选取最小的元素，将其作为有序序列的第i个元素，直到将所有元素都排序完。
时间复杂度： O ( n 2 ) O(n^2) O(n2)

void selectSort(vector<int>& array) {
    for (int i = 0; i < array.size(); i++) {
        int min = i;
        for (int j = i + 1; j < array.size(); j++) {
            if (array[min] > array[j]) {
                min = j;
            }
        }
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }
}

6、堆排序

基本思想：将待排序的n个元素建成初始堆，由于堆本身的特性，堆顶元素就是最大值。输出堆顶元素，然后将堆底元素送入堆顶，重复过程，依次将n个元素排序好。
时间复杂度： O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

void headAdjust(vector<int>& array, int k, int len) {
    int temp = array[k];
    for (int i = 2*k+1; i <= len; i = 2*i+1) {
        if (i < len && array[i] < array[i+1]) {
            i++;
        }
        if (temp > array[i]) {
            break;
        } else {
            array[k] = array[i];
            k = i;
        }
    }
    array[k] = temp;
}

void buildMaxHead(vector<int>& array, int len) {
    for (int i = (len-1)/2; i >= 0; i--) {
        headAdjust(array, i, len);
    }
}

void headSort(vector<int>& array) {
    buildMaxHead(array, array.size()-1);
    for (int i = array.size()-1; i > 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        headAdjust(array, 0, i-1);
    }
}

7、归并排序

基本思想：假定待排序表含有n个元素，则可将其视为n个有序的子表，每个子表的长度为1，然后两两归并，得到新的长度为2或1的子表，如此重复，直到合并为一个长度为n的有序表为止。
时间复杂度： O ( n l o g 2 n ) O(nlog_2n) O(nlog2​n)

void merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp(high - low + 1);
    int left = low, right = mid + 1;
    int index = 0;
    while (left <= mid && right <= high) {
        while (left <= mid && arr[left] <= arr[right]) {
            temp[index++] = arr[left++];
        }
        while (right <= high && arr[left] >= arr[right]) {
            temp[index++] = arr[right++];
        }
    }
    while (left <= mid) {
        temp[index++] = arr[left++];
    }
    while (right <= high) {
        temp[index++] = arr[right++];
    }
    for (int i = 0; i < temp.size(); i++) {
        arr[low + i] = temp[i];
    }
}

void mergeSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int mid = (low + high) >> 1;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

8、基数排序

基本思想：将待排序的元素拆分为多个关键字（比较两个元素时，先比较第一关键字，如果相同再比较第二关键字……），然后先对第一个关键字进行稳定排序，再对第二个关键字进行稳定排序，……最后对第N关键字进行稳定排序，这样就完成了对整个待排序序列的稳定排序。
时间复杂度： O ( d ∗ ( n + k ) ) O(d*(n+k)) O(d∗(n+k))，d是最大值的位数，k是进制

int getMaxBit(vector<int>& arr) {
    int max = arr[0];
    int bit = 0;
    for (int num : arr) {
        max = max > num ? max : num;
    }
    while (max > 0) {
        bit++;
        max /= 10;
    }
    return bit;
}

void radixSort(vector<int>& arr) {
    int max_bit = getMaxBit(arr);
    vector<int> count(10);
    vector<int> temp(arr.size());
    int radix = 1;
    for (int i = 0; i < max_bit; i++) {
        for (int j = 0; j < count.size(); j++) {
            count[j] = 0;
        }
        for (int num : arr) {
            int x = (num/radix)%10;
            count[x]++;
        }
        for (int j = 1; j < count.size(); j++) {
            count[j] = count[j-1] + count[j];
        }
        for (int j = arr.size() - 1; j >= 0; j--) {
            int x = (arr[j]/radix)%10;
            temp[count[x]-1] = arr[j];
            count[x]--;
        }
        for (int j = 0; j < arr.size(); j++) {
            arr[j] = temp[j];
        }
        radix = radix * 10;
    }
}