（1）冒泡排序
冒泡排序的思路是数小的像泡泡一样冒出来，反过来我们可以理解为，数大的像石头一样沉下去。
我们遍历数组，从左到右，若右边的数比左边的大，则交换。
第一遍：最大的数沉下去
第二遍：第二大的数沉在倒数第二个位置
…
版本二为常见常用版本，版本三在二的基础上优化，避免了不需要的排序
class Sloution { public: //冒泡：时间复杂度O(n^2) //把最小的数放在前面 vector<int> Bubble_Sort(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { //一直把最小的数放在第一位，第二小的数放在第二位，... if (nums[i] > nums[j]) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } } return nums; } //优化， 以下是最常用的冒泡，，，把最大的数放在后面 //上面的步骤会产生很多无效的排序，比如第一个数是2，最后一个数是1； 交换之后2放到最后面了。 第二次遍历又很麻烦 vector<int> Bubble_Sort02(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) { //修改这里 int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } return nums; } //优化2 vector<int> Bubble_Sort03(vector<int>& nums) { int n = nums.size(); bool flag = true; for (int i = 0; i < n - 1 && flag; i++) { flag = false; for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) { //修改这里 int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; flag = true; //每次循环i有修改，这里为true 如果跑了一次I没有发生交换的情况，说明已经排序完成，不需要再跑后面的i } } } return nums; } }
（2）选择排序
选择排序：选出最小的数，放在首位； 再次选，放在第二位， …
//选择排序：选出最小的数，放在首位； 再次选，放在第二位， ... //时间复杂度：O(n^2) 性能略优于冒泡排序 //类似于在冒泡1基础上改进 vector<int> Simple_Selection_Sort(vector<int>& nums) { int n = nums.size(); int min; for (int i = 0; i < n; i++) { min = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[min]) { min = j; } } int temp = nums[i]; nums[i] = nums[min]; nums[min] = temp; } return nums; }
（3）直接插入排序
vector<int> InsertSort(vector<int>& nums) { for (int i = 1; i < nums.size(); i++) { //从索引1开始 往前插入 int temp = nums[i]; int j = i - 1; for (j; j >= 0 && nums[j] > temp; j--) { //前面的数 > 后面的数, 实现后移 nums[j + 1] = nums[j]; } nums[j + 1] = temp; } return nums; }
时间复杂度：
最好的情况：所有数据是正序，每次排序都不用移动元素，此时为O(N)；
最坏的情况：所有数据都是倒序，每次都要将前面的元素后移，此时为O(N^2);
空间复杂度：
在排序的过程中，需要一个临时存储取出值的temp变量，所以空间复杂度为O(1)；
直接插入排序是稳定的排序算法，因为它不需要改变相同元素的位置；
（4）希尔排序
是在直接插入基础上进行改进，跳着插
//增量排序 //时间复杂度：O(n^1.5) vector<int> ShellSort(vector<int>& nums){ int n = nums.size(); int gap = n; //增量 while (gap > 1){ gap = gap / 3 + 1; //增量序列 for (int i = gap; i < n; i++){ int temp = nums[i]; int j = i - gap; for (j; j >= 0 && nums[j] > temp; j = j - gap){ //跳跃式前移 nums[j + gap] = nums[j]; } nums[j + gap] = temp; } } return nums; }
（5）堆排序
是对简单选择排序的改进
参考博客：博客链接，写的很清楚，就是看不懂…
先记录吧
class Sloution02 { public: void heapfi(vector<int>& nums, int n, int i) //对一颗完全二叉树的指定非叶子节点及其叶子结点进行堆的建立 { //int n = nums.size(); if (i >= n) { //如果i>=n的时候，证明数组中的元素都已经建立成大根堆了，这是递归终止标志 return; } int lchild = i * 2 + 1; //左孩子节点的下标 int rchild = i * 2 + 2; //右孩子节点的下标 int max = i; //默认数值最大的节点为该非叶子节点的值 if (lchild < n && nums[lchild] > nums[max]) { //判断左孩子节点是否在索引范围内及左孩子结点值是否大于根节点 max = lchild; //大于的话就将较大值的下标记录在max中 } if (rchild < n && nums[rchild] > nums[max]) { //同上 max = rchild; } if (max != i) { swap(nums[max], nums[i]); //如果最大值的下标改变，则需要交换两个下标所对应的值 heapfi(nums, n, max); //对剩下的不是完全二叉树的元素继续进行堆的建立， 套娃 } } void build_heap(vector<int>& nums) { int n = nums.size(); int last_node = n - 1; int parent = (last_node - 1) / 2; //从一棵树的最后一个非叶子节点开始建立堆 for (int i = parent; i >= 0; i--) { heapfi(nums, n, i); } } //堆排序 vector<int> heap_sort(vector<int>& nums) { int n = nums.size(); build_heap(nums); //先建立一个大根堆 for (int i = n - 1; i >= 0; i--) //循环交换大根堆中的第一个元素和最后一个元素，并将交换后的最后一个元素出局 { swap(nums[i], nums[0]); //交换第一个元素和最后一个元素 heapfi(nums, i, 0); //调整剩下元素的位置，构建一个新的大根堆，从i号元素开始，即是将交换后的最后一个元素出局 } return nums; } };
（6）桶排序
- 准备一个很大的容器，包含所有数出现的范围。比如就假设第一个容器就装0出现的次数，第二个容器装1出现的次数…
- 初始化容器里面的数都为0
- 然后遍历待排序的数组，比如数组中有两个0，然后标号为0的桶子就记录0出现的次数，即装2；出现一个5，就在标号为5的桶子里装1
- 再次遍历容器输出桶子里非零的桶子标号
挺简单的代码这里就不实现，并没有一个统一的模板，因数组大小不一样。
桶排序浪费空间
适用于没有过多重复元素的数组，时间复杂度大致看为O(n)
（7）基数排序
参考博客：链接
class Sloution03 { public: int MaxBit(vector<int>& input) //求出数组中最大数的位数 { int max_num = input[0]; //默认最大数为第一个数字 for (int i = 0; i < input.size(); i++) //找出数组中的最大数 { if (input[i] > max_num) { max_num = input[i]; } } int p = 0; while (max_num > 0) { p++; max_num /= 10; //每次除以10取整，即可去掉最低位 } return p; } int GetNum(int num, int d) //取出所给数字的第d位数字 { int p = 1; while (d - 1 > 0) { p *= 10; d--; } return num / p % 10; } //基数排序 vector<int> RadixSort(vector<int>& nums){ int n = nums.size(); vector<int> bucket(n); //创建临时存放排序过程中的数据 vector<int> count(10); //创建按位计数的技术容器，即记录排序中按个位、十位...各个数的位置的个数 for (int d = 1; d <= MaxBit(nums); d++) { // 计数器清0 for (int i = 0; i < 10; i++) { count[i] = 0; } // 统计各个桶中的个数 for (int i = 0; i < n; i++) { count[GetNum(nums[i], d)]++; } for (int i = 1; i < 10; i++) { //得到每个数应该放入bucket中的位置 count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { //采用倒序进行排序是为了不打乱已经排好的顺序 int k = GetNum(nums[i], d); bucket[count[k] - 1] = nums[i]; count[k]--; } for (int j = 0; j < n; j++) // 临时数组复制到 input 中 { nums[j] = bucket[j]; } } return nums; } };
（8）归并排序
该算法是典型的分治策略算法，基本思想是将待排序数组分成若干个小数组，直到为单个数组（即为有序数组）后（分阶段），再将前面得到的单个数组依次拼接在一起，组成有序数组（治阶段）。
动态效果示意图如下：
#include<iostream> #include<algorithm> using namespace std; void merge(int* data, int start, int end, int* result) { int left_length = (end - start + 1) / 2 + 1; int left_index = start; int right_index = start + left_length; int result_index = start; while (left_index < start + left_length && right_index < end + 1) //store data into new array { if (data[left_index] <= data[right_index]) result[result_index++] = data[left_index++]; else result[result_index++] = data[right_index++]; } while (left_index < start + left_length) result[result_index++] = data[left_index++]; while (right_index < end + 1) result[result_index++] = data[right_index++]; } void merge_sort(int* data, int start, int end, int* result) { if (1 == end - start) //last only two elements { if (data[start] > data[end]) { int temp = data[start]; data[start] = data[end]; data[end] = temp; } return; } else if (end == start) return; //last one element then there is no need to sort; else { //continue to divide the interval merge_sort(data, start, (end - start + 1) / 2 + start, result); merge_sort(data, (end - start + 1) / 2 + start + 1, end, result); //start to merge sorted data merge(data, start, end, result); for (int i = start; i <= end; ++i) { data[i] = result[i]; } } } //example int main() { int data[] = { 5,3,6,7,3,2,7,9,8,6,34,32,5,4,43,12,37 }; int length = 17; int result[17]; merge_sort(data, 0, length - 1, result); for (int i = 0; i < length; i++) cout << result[i] << ' '; system("pause"); return 0; }
class Sloution02 { public: void merge(int arr[], int left, int mid, int right){ int left_size = mid - left; int right_size = right - mid + 1; int left_num[100]; int right_num[100]; int i, j, k; //将输入的数组前半部分复制到left_num中 for (i = left; i < mid; i++){ left_num[i - left] = arr[i]; } //将输入的数组前半部分复制到right_num中 for (i = mid; i <= right; i++){ right_num[i - mid] = arr[i]; } //将上边的左右数组比较大小后合并到一个数组中 i = 0, j = 0, k = left; while (i < left_size && j < right_size){ if (left_num[i] < right_num[j]) {//按照从小到大的顺序将元素一次放到arr中 arr[k] = left_num[i]; i++; k++; } else{ arr[k] = right_num[j]; j++; k++; } } //如果右边部分的数组都放进arr中而左边部分的还有未放入的，就将左边剩余的全部放入 while (i < left_size) { arr[k] = left_num[i]; i++; k++; } while (j < right_size){ arr[k] = right_num[j]; j++; k++; } } void mergeSort(int arr[], int left, int right){ if (left == right){ return; } else { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid + 1, right); } } //int main() //{ // int arr[] = { 2, 5, 4, 3, 9, 1 }; // int left = 0; // int mid = 3; // int right = 5; // //merge(arr, left, mid, right); // mergeSort(arr, left, right); // for (int s = 0; s <= right; s++) // { // cout << arr[s]; // } // system("pause"); // return 0; //} };
二、算法分析：
1、时间复杂度
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
2、空间复杂度
由前面的算法说明可知，算法处理过程中，需要开辟两个临时数组分别用于存放原属数组的左右两部分。
3、算法稳定性
在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法
（9）快速排序
这里可以看书籍《啊哈算法》的讲解，很清楚
采用二分的思想
参考博客：链接
class Sloution04 { public: int part(vector<int>& list, int left, int right){ if (list.empty()){ return -1; } int base = list[left]; //从最左边的元素为中心元素 while (left < right) { while (left < right && list[right] > base) //判断右侧元素是否大于中心元素，大于就继续遍历 right--; list[left] = list[right]; //否则就将右侧小于中心元素的元素挪到左边的位置 while (left < right && list[left] < base) //判断左侧元素是否小于中心元素，小于就继续遍历 left++; list[right] = list[left]; //否则就将左侧小于中心元素的元素挪到右边的位置 } list[left] = base; //最后将中心元素放到左侧位置，此时left左边的元素都比base小 return left; } vector<int> QuickSort(vector<int>& list, int left, int right){ if (left < right){ int base = part(list, left, right); //对数组进行分割，得到分割后的下标 QuickSort(list, left, base - 1); //左边排序 QuickSort(list, base + 1, right); //右边排序 } return list; } };
