算法基础知识与十大排序

阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的，如果你不知道自己该看哪个部分的算法题，可以先看一下这里，戳我直达。

以下是本部分正文：

这里简单为大家讲解一下一些算法基础知识与十大排序，在面试考察中十大排序出现的频率是非常高的，特别是冒泡排序、快速排序、归并排序等，具体可点击这里

1、冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

C++
void bubbleSort(vector<int>& a, int n) {
    for (auto i = 0; i < n; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
}

时间复杂度 o(n^2) ，空间 o 1，原地算法，稳定

C++
void bubbleSort(vector<int>& nums) {

    int len = nums.size();
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) 
                swap(nums[j], nums[j + 1]);
        }
    }
}

冒泡优化版本

假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了。

C++
void bubbleSort2(vector<int>& nums) {

    int len = nums.size();
    bool flag = false;
    for (int i = 0; i < len; ++i) {
        flag = false;
        for (int j = 0; j < len - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) { 
                flag = true;
                swap(nums[j], nums[j + 1]); 
            }
        }
        if (!flag)//说明没有交换，则表明[0,len-i-1]已经是有序的了
            break;
    }
}

冒泡优化版本2.0

一位好心网友指出上述两个冒泡排序（包括优化版本），均存在一定问题：

1、两种冒泡排序（包括优化版本）都是循环了n次，虽然不影响结果的正确性，但对于n个元素的冒泡排序趟数， n - 1躺更符合规范理解一些；

现给出冒泡排序优化版本2.0

C++
#include <iostream>
#include <vector>

//using namespace std;

using std::cout;
using std::endl;
using std::vector;
using std::swap;

void print(vector<int>& nums) {
    for (auto i : nums) {
        cout << i << " ";
    }
    cout << endl;
}

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    bool flag = false;
    for (int i = 0; i < n - 1; ++i) {//i = 0 起，循环了n - 1趟，更符合规范理解
    //for (int i = 0; i < n; ++i) {//i = 0 起，循环了n 趟，不影响结果
        flag = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (nums[j] > nums[j + 1]) {
                //某一趟排序中，只要发生一次元素交换，flag就从false变为了true
                //也即表示这一趟排序还不能确定所剩待排序列是否已经有序，应继续下一趟循环
                swap(nums[j], nums[j + 1]);
                flag = true;
            }
        }
        //但若某一趟中一次元素交换都没有，即依然为flag = false
        //那么表明所剩待排序列已经有序
        //不必再进行趟数比较，外层循环应该结束，即此时if (!flag) break; 跳出循环
        /* if (flag) { break; } */
        if (!flag) { break; }
    }
}

int main() {
    vector<int> nums = { 8,9,1,4,2,3,6,7,5,5 };
    bubbleSort(nums);
    print(nums);

    return 0;
}

感谢微信好友“余往”给出指导意见，已采纳-2021.06.07

2、选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给>二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
以此类推，直到所有元素均排序完毕
时间负复杂度：O(n^2)，空间O（1），非稳定排序，原地排序

第二个动图演示

选择排序

代码

C++
void selectionSort(vector<int>& a, int n) {
    int minIndex;
    for (int i = 0; i < n; ++i) {
        minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[minIndex]) minIndex = j;
        }
        swap(a[i], a[minIndex]);    
    }
}

C++
void selectSort(vector<int>& nums) {
    int len = nums.size();
    int minIndex = 0;
    for (int i = 0; i < len; ++i) {
        minIndex = i;
        for (int j = i + 1; j < len; ++j) {
            if (nums[j] < nums[minIndex]) minIndex = j;
        }
        swap(nums[i], nums[minIndex]);
    }
}

3、插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。

当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

时间复杂度 on^2 空间 o1，稳定排序，原地排序

C++
void print(vector<int>& a, int n, int i) {
    cout << "step"<< i << ": ";
    for (int j = 0; j < n; j++) {
        cout << a[j] << " ";
    }
    cout << endl;
}
void insertionSort(vector<int>& a, int n) {//{ 9,1,5,6,2,3 }
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {   //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            int j = i - 1;
            int x = a[i];     //复制为哨兵，即存储待排序元素
            //a[i] = a[i - 1];           //先后移一个元素，可以不要这一句，跟循环里面的功能重复了
            while (j >= 0 && x < a[j]) {   //查找在有序表的插入位置,还必须要保证j是>=0的 因为a[j]要合法
                a[j + 1] = a[j];
                j--;     //元素后移
            }
            a[j + 1] = x;     //插入到正确位置
        }

        print(a, n, i);      //打印每趟排序的结果
    }
}

4、快速排序不太好记住

算法思想

1、选取第一个数为基准

2、将比基准小的数交换到前面，比基准大的数交换到后面

3、对左右区间重复第二步，直到各区间只有一个数

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

为方便理解我还准备了动图：

C++
void quickSort(vector<int>& a, int low, int high) {
    if (low >= high)        // 结束标志
        return;
    int first = low;        // 低位下标
    int last = high;        // 高位下标
    int key = a[first];     // 设第一个为基准

    while (first < last)
    {
        // 从后往前走，将比第一个小的移到前面
        while (first < last && a[last] > key)
            last--;
        if (first < last)
            a[first++] = a[last];

        //从前往后走， 将比第一个大的移到后面
        while (first < last && a[first] <= key)
            first++;
        if (first < last)
            a[last--] = a[first];
    }

    a[first] = key;
    // 前半递归
    quickSort(a, low, first - 1);
    // 后半递归
    quickSort(a, first + 1, high);

}


quickSort(A, 0,A.size()-1);
    for (auto a : A) {
        cout << a << endl;
    }

自己复写一遍，加强了理解

C++
void quickSort(vector<int>&numbers, int low, int high) {
    //  numbers = {10,8,4,6,9,10,123,6,2,14,3,8,5};
    if (low >= high) return;
    int first = low, last = high, key = numbers[low];
    cout << low << " " << high << " "<<key << endl;
    for (int i = 0; i < numbers.size(); ++i) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    while (first < last) {
        //从后往前找比他小的放前面,从前往后找比他大的放在后面，
        //以第一个数为基准，必须先从后往前走，再从前往后走

        while (first < last && numbers[last] >= key)
            last--;
        if (first < last) numbers[first++] = numbers[last];


        while (first < last && numbers[first] <= key)
            first++;
        if (first < last) numbers[last--] = numbers[first];

    }
    numbers[first] = key;

    cout << "the index " << first << "  value " << key << endl;

    quickSort(numbers, low, first - 1);
    quickSort(numbers, first + 1, high);
}

再一次复写

C++
void quickSort2(vector<int>& nums, int begin, int end) {
    if (begin >= end) return;//4,10,3,0,5,1,2
    int first = begin, last = end;
    int key = nums[first];
    while (first < last) {
        while (first < last && nums[last] >= key)
            last--;
        if (first < last)
            nums[first++] = nums[last];

        while (first < last && nums[first] <= key)
            first++;
        if (first < last)
            nums[last--] = nums[first];
    }

    nums[first] = key;
    cout << begin << " " << end << " " << key << endl;
    for (auto a : nums)
        cout << a << " ";
    cout << endl << endl;


    quickSort2(nums, begin, first-1);
    quickSort2(nums, first+1, end);

}

再次复写

C++
void print(vector<int>& nums) {
    for (auto a : nums)
        cout << a << " ";
    cout << endl;

}
void quickSort(vector<int>& nums, int begin, int end) {
    if (begin >= end) return;
    int low = begin, high = end, key = nums[begin];
    while (low < high) {
        while (low < high && nums[high] >= key) {
            high--;

        }
        if (low < high)  nums[low++] = nums[high];

        while (low < high && nums[low] <= key) {
            low++;

        }
        if (low < high)  nums[high--] = nums[low];
    }

    nums[low] = key;
    print(nums);

    quickSort(nums, begin, low - 1);
    quickSort(nums, low + 1, end);

}

5、希尔排序

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。

希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。

希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

为方便理解我还准备了图片：

如果还是不懂的话我还给你准备了优质的文章讲解：https://mp.weixin.qq.com/s/4kJdzLB7qO1sES2FEW0Low

C++
void shellSortCore(vector<int>& nums, int gap, int i) {
    int inserted = nums[i];
    int j;
    //  插入的时候按组进行插入
    for (j = i - gap; j >= 0 && inserted < nums[j]; j -= gap) {
        nums[j + gap] = nums[j];
    }
    nums[j + gap] = inserted;
}

void shellSort(vector<int>& nums) {
    int len = nums.size();
    //进行分组，最开始的时候，gap为数组长度一半
    for (int gap = len / 2; gap > 0; gap /= 2) {
        //对各个分组进行插入分组
        for (int i = gap; i < len; ++i) {
            //将nums[i]插入到所在分组正确的位置上
            shellSortCore(nums,gap,i);
        }
    }

    for (auto a : nums) {
        cout << a << "";
    }

}

6、归并排序

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。

通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

第二个演示动图

算法思想

1、把长度为n的输入序列分成两个长度为n/2的子序列；

2、对这两个子序列分别采用归并排序；

3、将两个排序好的子序列合并成一个最终的排序序列。

1、// 归并排序（C++-迭代版）

C++
template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            cout << low << " " << mid << " " << high << endl;
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }

        swap(a, b); //交换a b 地址
        //T* temp = a;
        //  a = b;
        //  b = temp;

    }

    //if (a != arr) {
    //  for (int i = 0; i < len; i++)
    //      b[i] = a[i];
    //  b = a;
    //}

    /*
    十分严谨的一种安排
    每次排序都要交换 a、b 值（数组首地址）
1、if(a != arr)：如果排序结束后，a 值为原来数组 b 首地址，此时 arr 与 b 相同，arr 数组内容不是最终的结果，
2、循环内容：把 a数组内容复制到数组 b（数组arr）
3、b = a ：循环结束后，让 b 指向它原来的数组首地址，以便 delete[]

    */
    delete[] b;
}

2、// 归并排序（C++-递归版）

C++
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) {
    T reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

3、vector 类型的递归，就记这一种

C++
void mergeSortCore(vector<int>& data, vector<int>& dataTemp, int low, int high) {

    if (low >= high) return;
    int len = high - low, mid = low + len / 2;
    int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;
    mergeSortCore(data, dataTemp, start1, end1);
    mergeSortCore(data, dataTemp, start2, end2);
    int index = low;
    while (start1 <= end1 && start2 <= end2) {
        dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];
    }

    while (start1 <= end1) {
        dataTemp[index++] = data[start1++];
    }


    while (start2 <= end2) {
        dataTemp[index++] = data[start2++];
    }

    for (index = low; index <= high; ++index) {
        data[index] = dataTemp[index];
    }
}


void mergeSort(vector<int>& data) {
    int len = data.size();
    vector<int> dataTemp(len, 0);
    mergeSortCore(data, dataTemp, 0, len - 1);
}

节约时间的一种递归归并排序，很好，也记这一种：

C++
void mergeSortCore(vector<int>& nums, vector<int>& copy, int begin, int end) {
    if (begin >= end) return;
    int mid = begin + (end - begin) / 2;
    int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end;
    mergeSortCore(copy, nums, low1, high1);//这里减少了copy向nums的赋值部分，千万注意不要把copy 和 nums赋值反了
    mergeSortCore(copy, nums, low2, high2);

    int copyIndex = low1;
    while (low1 <= high1 && low2 <= high2) {
        copy[copyIndex++] = nums[low1] < nums[low2] ? nums[low1++] : nums[low2++];
    }
    while (low1 <= high1) {
        copy[copyIndex++] = nums[low1++];
    }
    while (low2 <= high2) {
        copy[copyIndex++] = nums[low2++];
    }

    cout << begin << " " << end << endl;
    for (auto a : copy) {
        cout << a << " ";
    }
    cout << endl;

}

void mergeSort(vector<int> nums) {

    for (auto a : nums) {
        cout << a << " ";
    }
    cout << endl;


    vector<int> copyNums(nums);//这里要借助一个一模一样的数组的
    mergeSortCore(nums, copyNums, 0, nums.size() - 1);
    nums.assign(copyNums.begin(), copyNums.end());//到最后copy数组是排序好的，记得要赋值一下

    for (auto a : nums) {
        cout << a << " ";
    }
}

复写

C++
void print(vector<int>& nums) {
    for (auto a : nums)
        cout << a << " ";
    cout << endl;

}

void mergeSort(vector<int>& data, vector<int>&temp,int begin,int end) {
    if (begin >= end) return;
    int low1 = begin, high2 = end, mid = begin + (end - begin) / 2;
    int high1 = mid, low2 = mid + 1;
    print(data);
    mergeSort(temp, data, low1, high1);
    mergeSort(temp, data, low2, high2);
    int index = low1;
    while (low1 <= high1 && low2 <= high2) {
        temp[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
    }
    while (low1 <= high1) {
        temp[index++] = data[low1++];
    }

    while (low2 <= high2) {
        temp[index++] = data[low2++];
    }

}

void main(){


    vector<int> nums = { 5,3,5,6,1,4,9,10,6,2};
    vector<int> temp(nums);
    mergeSort(nums,temp , 0, nums.size() - 1);
    nums.assign(temp.begin(),temp.end());
}

4、vector 类型的迭代

C++
void mergeSort(vector<int>& data) {
    int len = data.size();
    vector<int> dataTemp(len, 0);
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {

            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int index = low, start1 = low, end1 = mid, start2 = mid, end2 = high;

            while (start1 < end1 && start2 < end2) {
                dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];
            }

            while (start1 < end1) {
                dataTemp[index++] = data[start1++];
            }


            while (start2 < end2) {
                dataTemp[index++] = data[start2++];
            }

        }
        swap(data, dataTemp);
    }

    for (auto a : data)
        cout << a << " ";   
}

7、堆排序

看到两个比较好的讲解堆排序的B站视频

1、堆排序(heapsort)：https://www.bilibili.com/video/BV1Eb41147dK?from=search&seid=3993837508839965022

2、十分钟搞定堆排序：https://www.bilibili.com/video/BV1vt4y1y7wR?from=search&seid=3993837508839965022

C++
void heapify(vector<int>& nums, int n, int i)//对有一定顺序的堆，
//当前第i个结点取根左右的最大值（这个操作称heapfiy）
{
    int l = i * 2 + 1, r = i * 2 + 2;
    int max = i;
    if (l<n && nums[l]>nums[max])
        max = l;
    if (r<n && nums[r]>nums[max])
        max = r;
    if (max != i)
    {
        swap(nums[max], nums[i]);
        heapify(nums, n, max);
    }
}
void heapify_build(vector<int>& nums, int n)//建立大根堆，从树的倒数第二层第一个结点开始，
//对每个结点进行heapify操作，然后向上走
{
    int temp = (n - 2) / 2;
    for (int i = temp; i >= 0; i--)
        heapify(nums, n, i);

    for (int i = 0; i < nums.size(); i++)
        cout << nums[i] << " ";
    cout << endl;
}
void heapify_sort(vector<int>& nums, int n)//建立大根堆之后，每次交换最后一个结点和根节点（最大值），
//对交换后的根节点继续进行heapify（此时堆的最后一位是最大值，因此不用管他，n变为n-1）
{
    heapify_build(nums, n);
    for (int i = 0; i < n; i++)
    {
        swap(nums.front(), nums[n - i - 1]);
        heapify(nums, n - i - 1, 0);
    }
}

8、计数排序

计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
如果 k（待排数组的最大值）过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
计数排序不是比较排序，排序的速度快于任何比较排序算法。

算法思想：

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

计数排序

代码

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
    // 确保待排序容器非空
    if (vecRaw.size() == 0)
        return;

    // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
    int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
    vector<int> vecCount(vecCountLength, 0);

    // 统计每个键值出现的次数
    for (int i = 0; i < vecRaw.size(); i++)
        vecCount[vecRaw[i]]++;

    // 后面的键值出现的位置为前面所有键值出现的次数之和
    for (int i = 1; i < vecCountLength; i++)
        vecCount[i] += vecCount[i - 1];

    // 将键值放到目标位置
    for (int i = vecRaw.size(); i > 0; i--) // 此处逆序是为了保持相同键值的稳定性
        vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

int main()
{
    vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
    vector<int> vecObj(vecRaw.size(), 0);

    CountSort(vecRaw, vecObj);

    for (int i = 0; i < vecObj.size(); ++i)
        cout << vecObj[i] << "  ";
    cout << endl;

    return 0;
}

9、桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。

算法思想：

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

桶排序

PHP
function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);
        }
    }

    return arr;
}

10、基数排序

一种多关键字的排序算法，可用桶排序实现。

算法思想：

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）

基数排序

代码

C++
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];      ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

参考资料

https://mp.weixin.qq.com/s/ekGdneZrMa23ALxt5mvKpQ

https://www.cnblogs.com/onepixel/p/7674659.md（部分动图来源）

https://visualgo.net/zh/sorting?slide=10-2

算法基础知识与十大排序

1、冒泡排序

2、选择排序

3、插入排序

4、快速排序 不太好记住

5、希尔排序

6、归并排序

1、// 归并排序（C++-迭代版）

2、// 归并排序（C++-递归版）

3、vector 类型的递归 ，就记这一种

4、vector 类型的迭代

7、堆排序

8、计数排序

9、桶排序

10、基数排序

参考资料

4、快速排序不太好记住

3、vector 类型的递归，就记这一种