各种排序算法

#include <iostream>
#include <vector>
using namespace std;

// 打印 vector
void printVector(vector<int> &valVec) {
    for (int i = 0; i< valVec.size(); i++) {
        printf("%d ", valVec[i]);
    }
}

// 构造待排序数组
vector<int> constructVec() {
    vector<int> vec;
    vec.push_back(6);
    vec.push_back(2);
    vec.push_back(1);
    vec.push_back(9);
    vec.push_back(5);
    return vec;
}

// 冒泡排序
void bubbleSort(vector<int> &vec) {
    if (vec.size() <= 1) {
        return;
    }
    
    int len = (int)vec.size();
    for (int i = 0; i < len - 1; i++) { /// n - 1 轮，每轮将最大的数挪到最后！！！
        for (int j = 0; j < len - 1 - i; j++) { // 注意这里减去 i
            if (vec[j] > vec[j+1]) {
                int tmp = vec[j];
                vec[j] = vec[j+1];
                vec[j+1] = tmp;
            }
        }
    }
}

// 选择排序
void selectionSort(vector<int> &vec) {
    if (vec.size() <= 1) {
        return;
    }
    
    int len = (int)vec.size();
    for (int i = 0; i < len; i ++) { /// n 轮，每轮获取最小的树放在最前！！！
        int minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (vec[j] < vec[minIndex]) {
                minIndex = j;
            }
        }
        int tmp = vec[minIndex];
        vec[minIndex] = vec[i];
        vec[i] = tmp;
    }
}

// 插入排序（折半排序）：https://www.runoob.com/w3cnote/insertion-sort.html
void insertSort(vector<int> &vec) {
    /// 每轮将后一个元素插入到前面已排序的数组中！！！
    for (int i = 1; i < vec.size(); i++) {
        int elementI = vec[i];
        int j = i - 1;
        // 如果 elementI 比前面的小，就 elementI 一直往前挪(其他元素往后一个位置挪)
        while(j >= 0 && vec[j] > elementI) {
            vec[j + 1] = vec[j];
            j--;
        }
        vec[j + 1] = elementI;
    }
}

// 归并排序：https://blog.csdn.net/weixin_54913371/article/details/119654906
void innerMergeSort(vector<int> &vec, int start, int mid, int end) {
    int i = start;
    int j = mid + 1;
    
    // 合并两个排序数组，放在tmp数组中
    vector<int> tmp(end - start + 1);
    int k = 0;
    while (i <= mid && j <= end) {
        if (vec[i] < vec[j]) {
            tmp[k] = vec[i];
            k++;
            i++;
        } else {
            tmp[k] = vec[j];
            k++;
            j++;
        }
    }
    
    while (i <= mid) {
        tmp[k] = vec[i];
        k++;
        i++;
    }
    
    while (j <= end) {
        tmp[k] = vec[j];
        k++;
        j++;
    }
    
    // 合并后放回原数组容器中
    for (int l = 0; l < k; l++) {
        vec[start] = tmp[l];
        start++;
    }
}

void mergeSort(vector<int> &vec, int start, int end) {
    if (start == end) {
        return;
    }
    int mid = (start + end) / 2;
    mergeSort(vec, start, mid);
    mergeSort(vec, mid + 1, end);
    innerMergeSort(vec, start, mid, end);
}

// 快速排序：https://www.runoob.com/w3cnote/quick-sort.html
// 基本思想是找一个基准值，把小于基准值的放在其左侧，大于基准值的放在右侧。然后针对左右两侧递归重复刚才的操作
void quickSort(vector<int> &vec, int start, int end) {
    if (start < end) {
        int i = start;
        int j = end;
        int first = vec[i];
        
        while(i < j) {
            // 从右往左找，找到一个比 first 小的值
            while (j > i && vec[j] >= first) {
                j--;
            }
            if (j > i) {
                vec[i] = vec[j];
                i++;
            }
            
            // 从左往右找，找到一个比 first 大的值
            while (j > i && vec[i] <= first) {
                i++;
            }
            if (j > i) {
                vec[j] = vec[i];
                j--;
            }
        }
        vec[i] = first;
        quickSort(vec, 0, i - 1);
        quickSort(vec, i + 1, end);
    }
}

// 堆排序
// 堆的概念介绍（聚焦最大堆，内含堆插入节点，删除节点）：https://www.cnblogs.com/skywang12345/p/3610187.html
// 堆排序的实现（说得很详细清晰，内含c++算法代码）：https://www.jianshu.com/p/938789fde325
// 堆排序的步骤：1、构造最大堆。2、每次将最大元素挪到数组末，然后再将前面的元素调整为最大堆

void adjustHeap(vector<int> &vec, int rootIndex, int len) {
    int childIndex = 2 * rootIndex + 1;
    int rootValue = vec[rootIndex];
    while (childIndex < len) {
        // 挑选左右子节点最大的那个
        if (childIndex + 1 < len && vec[childIndex + 1] > vec[childIndex]) {
            childIndex++;
        }
        
        // 看看父节点和最大的子节点是否需要交换
        if (rootValue >= vec[childIndex]) {  // 无需交换
            break;
        } else {
            int tmp = rootValue;
            vec[rootIndex] = vec[childIndex];
            vec[childIndex] = tmp;
            
            // 根节点下沉后的子节点，作为新的一轮根节点，继续看看是否需要下沉
            rootIndex = childIndex;
            childIndex = 2 * rootIndex + 1;;
        }
        
    }
}

void headSort(vector<int> &vec) {
    int len = (int)vec.size();
    
    // 构造最大堆
    for (int i = len / 2; i >= 0; i--) {
        adjustHeap(vec, (int)i, (int)len);
    }
    
    for (int i = len - 1; i > 0; i--) {
        // 将最大元素挪到数组末
        int tmp = vec[i];
        vec[i] = vec[0];
        vec[0] = tmp;
        
        // 调整除最大元素的其他元素为最大堆
        adjustHeap(vec, 0, (int)i);
    }
}

int main(int argc, const char * argv[]) {
    
    std::cout << "\n\n冒泡排序------ \n";
    vector<int> vec1 = constructVec();
    bubbleSort(vec1);
    printVector(vec1);
    
    std::cout << "\n\n选择排序------ \n";
    vector<int> vec2 = constructVec();
    selectionSort(vec2);
    printVector(vec2);
    
    std::cout << "\n\n插入排序------ \n";
    vector<int> vec3 = constructVec();
    insertSort(vec3);
    printVector(vec3);
    
    std::cout << "\n\n快速排序------ \n";
    vector<int> vec4 = constructVec();
    quickSort(vec4, 0, (int)(vec4.size() - 1));
    printVector(vec4);
    
    std::cout << "\n\n归并排序------ \n";
    vector<int> vec5 = constructVec();
    mergeSort(vec5, 0, (int)vec5.size() - 1);
    printVector(vec5);
    
    std::cout << "\n\n堆排序------ \n";
    vector<int> vec6 = constructVec();
    headSort(vec6);
    printVector(vec6);
    
    std::cout << "\n\n结束程序------ \n";
    
    return 0;
}