目录
一、冒泡排序：
实现代码：
基本原理：
二、直接插入排序
实现代码：
基本原理：
三、折半插入排序
实现代码：
基本原理：
四、简单选择排序
实现代码：
基本原理：
五、归并排序
实现代码：
基本原理：
六、希尔排序
实现代码：
基本原理：
七、基数排序
实现代码：
基本原理：
八、快速排序
实现代码：
基本原理：
九、堆排序
实现代码：
基本原理：
一、冒泡排序：
实现代码：
void bubble_Sort(vector<int> &nums){bool flag;for(int i=1;i < nums.size(); ++i){flag = false;for(int j=nums.size()-1;j >= i; --j){if(nums[j]<nums[j-1]){swap(nums[j], nums[j-1]);flag = true;}}if(flag == false){return ;}}
}基本原理：
在数组中，永远选择最后的一个元素，让其向前移动。如果它比前一个元素小则与之交换位置，从而到达移动的目的。
优化点：当一个元素经过一次循环都没有移动，又因为总是从最后位置移动，说明此元素是最大的元素，进而表示排序已经完成，可以提前结束。
二、直接插入排序
实现代码：
void insert_sort(vector<int> &nums){nums.insert(nums.begin(), 0);int i,j;for(i=2;i < nums.size();++i){nums[0] = nums[i];//哨兵，防止越界for(j=i-1;nums[j]>nums[0];--j){nums[j+1] = nums[j];}nums[j+1] = nums[0];}nums.erase(nums.begin());
}基本原理：
在数组中从前往后依次选择一个元素，将此元素插入到前面中的一个合适位置。每一次循环，都会让数组最前面i个元素变得有序，那么在插入第i+1个元素时，就能很容易找到前面i个位置中的合适位置放置此元素。
优化点：哨兵设置，减少了越界判断，但又保证了不会越界。
三、折半插入排序
实现代码：
void binary_Insert_Sort(vector<int> &nums){nums.insert(nums.begin(), 0);int i,j;int low, high, mid;for(i=2;i < nums.size();++i){nums[0] = nums[i];//哨兵，防止越界low = 1;high = i-1;while(low <= high){mid = (low+high) / 2;if(nums[mid] > nums[0]){high = mid-1;}else{low = mid+1;}}for(j=i-1;j >= high+1 ;--j){nums[j+1] = nums[j];}nums[high+1] = nums[0];}nums.erase(nums.begin());
}基本原理：
基于直接插入排序，更好的利用了前i个元素的有序性，通过二分法能比顺序法更快定位合适的插入位置
优化点：二分优化
四、简单选择排序
实现代码：
void select_Sort(vector<int> &nums){int min;for(int i=0;i < nums.size();++i){min = i;for(int j=i+1;j < nums.size();++j){if(nums[min] > nums[j]){min = j;}}if(min != i){swap(nums[i], nums[min]);}}
}基本原理：
不停的从当前位置至最后位置的元素中，找到一个最小元素，用于与当前位置元素交换位置。
五、归并排序
实现代码：
void merge_sort(vector<int> &nums){merge_step(nums, 0, nums.size()-1);
}void merge_step(vector<int> &nums, int _begin, int _end){if(_end - _begin < 1)return ;if(_end - _begin == 1){if(nums[_begin] > nums[_end]){swap(nums[_begin], nums[_end]);}return ;}int mid = (_begin+_end)/2;merge_step(nums, _begin, mid);merge_step(nums, mid+1, _end);vector<int> left_arr(nums.begin()+_begin, nums.begin()+mid+1);vector<int> right_arr(nums.begin()+mid+1, nums.begin()+_end+1);int left_tag = 0;int right_tag = 0;int cur = _begin;while(left_tag < (mid-_begin+1) && right_tag < (_end-mid)){if(left_arr[left_tag] < right_arr[right_tag]){nums[cur++] = left_arr[left_tag++];}else{nums[cur++] = right_arr[right_tag++];}}for(int i=left_tag;i < (mid-_begin+1);++i){nums[cur++] = left_arr[i];}for(int i=right_tag;i < (_end-mid);++i){nums[cur++] = right_arr[i];}
}基本原理：
采用分治的办法，递归的划分两个子数组并排序子数组，最后自底向上的有序的合并子数组。
六、希尔排序
实现代码：
void shell_sort(vector<int> &nums){for(int gap = nums.size()/2;gap > 0;gap/=2){for(int i = gap;i < nums.size();i += 1){for(int j=i; j >= gap && nums[j-gap] > nums[j];j-=gap){swap(nums[j], nums[j-gap]);}}}
}基本原理：
通俗的而言，就是先让元素以较快的速度移动向自己最终位置，但是移动过程中，随着距离的减少，当前过快的速度就无法恰好达到该位置，因此速度也要逐渐变慢。希尔排序中的"速度"就是移动的增量，是折半减少的。就仿佛一辆汽车快到达终点，要慢慢放低速度，不然就会错过终点。
七、基数排序
实现代码：
void radix_sort(vector<int> &nums){int max_e = *max_element(nums.begin(), nums.end());int n = getLen(max_e);radix_step(nums, n);
}void radix_step(vector<int> &nums, int n){list<int> bin[10];list<int> temp(nums.begin(), nums.end());for(int i=1;i <= n;++i){for (std::list<int>::iterator it = temp.begin(); it != temp.end(); it++){int idx = getHashLocate(*it, n);bin[idx].push_back(*it);}temp.clear();for(int i=0;i < 10;++i){temp.insert(temp.end(), bin[i].begin(), bin[i].end());}}nums.clear();nums.insert(nums.begin(), temp.begin(), temp.end());
}基本原理：
依靠元素的数位进行排序，就像分割了若干个桶，第i个桶装的是当前第k位上为i的所有数子。就这样不断的分发入桶，再取出，再分发入桶...最终就是一个有序的数组。思想是分块排序
八、快速排序
实现代码：
void quick_sort(vector<int> &nums){quick_step(nums, 0, nums.size()-1);
}void quick_step(vector<int> &nums, int begin, int end){int x = begin;int left = begin, right = end;if(end - begin <= 1){return ;}while(left < right){while(left < right && nums[x] <= nums[right])right--;if(left > right)break;swap(nums[x], nums[right]);x = right;while(left < right && nums[x] >= nums[left])left++;if(left > right)break;swap(nums[x], nums[left]);x = left;}quick_step(nums, begin, x);quick_step(nums, x+1, end);
}基本原理：
以一个元素为基准，将其他元素分割成两部分，一部分的元素小于等于这个基准，另一部分则大于这个基准。然后再分别对这两部分进行如上操作。
九、堆排序
实现代码：
大小根堆(模板)完整实现
基本原理：
代码中有一些简要的注释
优化点：大小根堆的融合，采用负数逆转方法，从而将大小根堆合二为一，但本质上是利用大根堆实现了小根堆的功能。