- 选择排序 <不稳定>
首先找到序列中最小的元素并将它与序列中第一个元素交换，最小元素归位。然后从第二个元素开始扫描，找到剩下n-1个元素中最小的元素与第二个元素交换，将第二小元素归位。以此类推，扫描n-1遍后排序完成。
// 最小元素先归位
void selectSort(vector<int>& nums){
int n = nums.size();
for(int i=0; i<n-1; i++){
int minIdx = i;
for(int j=i+1; j<n; j++){
if(nums[j]<nums[minIdx]){
minIdx = j;
}
}
swap(nums[i], nums[minIdx]);
}
}
- 冒泡排序 <稳定>
依次比较相邻的两个数，将小数放前，大数放后。即：
- 首先比较第1个数和第2个数，将小数放前，大数放后，然后比较第2个数和第3个数，将小数放前，大数放后，直至比较最后两个数，将小数放前，大数放后，至此第一趟结束，将最大的数放在了最后。
- 仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束。
- 重复以上过程，直至完成排序。
第i遍需要扫描的元素下标范围为[0, n-1-i)
// 最大元素先归位
void bubbleSort(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]){
swap(nums[j], nums[j+1]);
}
}
}
}
- 插入排序 <稳定>
- 从第一个元素开始，该元素被认为已经排序。
- 取出下一个元素（新元素），在已排序的序列中从后向前扫描，如果新元素小于已排序的元素，则将已排序元素后移一位，直到找到已排序元素小于或等于新元素的位置
- 将新元素放到该位置。
// 先从第一个元素开始，被认为已排序
void insertSort(vector<int>& nums){
int n = nums.size();
for(int i=1; i<n; i++){
int cur = nums[i];
int j=i;
while(j>0 && cur<nums[j-1]){
nums[j] = nums[j-1];
j--;
}
nums[j] = cur;
}
}
- 归并排序 <稳定>
归并排序算法在接近数组中间的位置划分数组，然后使用递归运算对两个一半元素构成的数组进行排序，最后将两个有序子数组进行合并，形成一个新的已排好序的数组。
void merge(vector<int>& nums, int left, int mid, int right){
int n = right - left + 1;
vector<int> tmp(n); //临时存放合并后的有序数组
int k = 0;
int l=left, r=mid+1;
while(l<=mid && r<=right){
tmp[k++] = nums[l]<=nums[r] ? nums[l++] : nums[r++];
}
while(l<=mid){
tmp[k++] = nums[l++];
}
while(r<=right){
tmp[k++] = nums[r++];
}
for(int i=0; i<n; i++){
nums[left+i] = tmp[i];
}
}
void mergeSort(vector<int>& nums, int left, int right){
if(left == right) return;
int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid+1, right);
merge(nums, left, mid, right);
}
int main(){
vector<int> nums = {3,4,2,1,5};
mergeSort(nums, 0, nums.size()-1);
for(int i=0; i<nums.size(); i++)
cout<<nums[i]<<' ';
return 0;
}
- 快速排序 <不稳定>
快速排序与合并排序有着很多相似性。将要排序的数组分成两个子数组，通过两次递归调用分别对两个数组进行排序，再将已经排好序的两个数组合并成一个独立的有序数组。但是，将数组一分为二的做法比合并排序中使用的方法复杂。它需要将所有小于或者等于基准元素的元素放置到基准元素前面的位置，将大于基准的元素放置到基准后面的位置。快速排序按照元素值大小拆分，得到两个分区（Partition）,拆分处称为分裂点（Split position）.
int partition(vector<int>& nums, int left, int right){
int p = nums[left];
int i=left, j=right;
while(i<j){
while(i<j && nums[j]>=p) j--;
while(i<j && nums[i]<=p) i++;
if(i<j){
swap(nums[i], nums[j]);
}
}
swap(nums[left], nums[i]);
return i; //返回分类点下标
}
void quickSort(vector<int>& nums, int left, int right){
if(left<right){
int q = partition(nums, left, right);
quickSort(nums, left, q-1);
quickSort(nums, q+1, right);
}
}
int main(){
vector<int> nums = {3,4,2,1,5};
quickSort(nums, 0, nums.size()-1);
for(int i=0; i<nums.size(); i++)
cout<<nums[i]<<' ';
return 0;
}
快速排序扩展：找出n个元素中第k小的元素
#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int>& nums, int left, int right){
int p = nums[left];
int i=left, j=right;
while(i<j){
while(i<j && nums[j]>=p) j--;
while(i<j && nums[i]<=p) i++;
if(i<j){
swap(nums[i], nums[j]);
}
}
swap(nums[left], nums[i]);
return i;
}
int randomPartition(vector<int>& nums, int left, int right){
int i = rand() % (right - left + 1) + left;
swap(nums[left], nums[i]);
return partition(nums, left, right);
}
int quickSelect(vector<int>& nums, int left, int right, int k){
int q = randomPartition(nums, left, right);
if(k==q) return nums[q];
else if(k>q) return quickSelect(nums, q+1, right, k);
else return quickSelect(nums, left, q-1, k);
}
int main(){
vector<int> nums = {3,3,3,3,3};
int k = 2;
int ans = quickSelect(nums, 0, nums.size()-1, k);
cout<<ans<<endl;
return 0;
}
- 堆排序
堆排序的思想是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于其子节点。此时整个序列最大值为堆顶元素，将堆顶元素与末尾元素交换，使得末尾元素为最大值，然后再调整堆顶元素使得剩下的n-1个元素仍为大根堆，再重复执行以上操作。
堆是一种完全二叉树。
void maxHeap(vector<int>& nums, int i, int end){
while(2*i+1<=end){
int lson = 2*i+1;
int rson = 2*i+2;
int large;
if(lson<=end && nums[lson]>nums[i]) large = lson;
else large = i;
if(rson<=end && nums[rson]>nums[large]) large = rson;
if(large != i){
swap(nums[i], nums[large]);
i = large;
}else{
break; //调整完毕
}
}
}
void heapSort(vector<int>& nums){
int n = nums.size();
//从最后一个父节点开始调整,先建成大根堆
for(int i=n/2-1; i>=0; i--){
maxHeap(nums, i, n-1);
}
for(int i=n-1; i>=1; i--){
swap(nums[0], nums[i]); //将堆顶元素与末尾元素交换
int end = i-1; //剩下n-1个元素排序
maxHeap(nums, 0, end);
}
}
