排序算法 C++

1、代码 

#include <iostream>
#include <vector>
using namespace std;
//冒泡排序
void bubble_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size() - 1; i++) { // times
        for (int j = 0; j < nums.size() - i - 1; j++) { // position
            if (nums[j] > nums[j + 1]) {
                swap(nums[j],nums[j + 1]);
            }
        }
    }
}

//选择排序
//首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
//再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
//重复第二步，直到所有元素均排序完毕。
void selection_sort(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++) { // position
        int min = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums[i], nums[min]);
    }
}

//插入排序
//将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
//从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与
//有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

void insert_sort(vector<int> &nums)
{
    for (int i = 1; i < nums.size(); i++) { // position
        for (int j = i; j > 0; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums[j],nums[j - 1]);
            }
        }
    }
}

//希尔排序
void shell_sort(vector<int>& num){
    for(int gap = num.size()/2; gap > 0; gap /= 2){
        for(int i = gap; i < num.size(); ++i){//插入排序
            for(int j = i - gap; j >= 0; j = j - gap){
                if(num[j] > num[j + gap])
                    swap(num[j], num[j + gap]);
            }
        }
    }
}

void merge(vector<int> &data, int start, int mid, int end) {
    vector<int> tmp;
    int i = start, j = mid + 1;
    while (i != mid + 1 && j != end + 1) {
        if (data[i] <= data[j]) {
            tmp.push_back(data[i++]);
        } else {
            tmp.push_back(data[j++]);
        }
    }
    while (i != mid + 1) {
        tmp.push_back(data[i++]);
    }
    while (j != end + 1) {
        tmp.push_back(data[j++]);
    }
    for (int i = 0; i < tmp.size(); i++) {
        data[start + i] = tmp[i];
    }
}
//归并排序
void merge_sort(vector<int> &data, int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(data, start, mid);
        merge_sort(data, mid + 1, end);
        merge(data, start, mid, end);
    }
}

int partition(vector<int>& nums, int low, int high)
{
    int pivotkey = nums[low];
    while(low < high)
    {
        while(low < high && nums[high] >= pivotkey)
            high--;
        swap(nums[low], nums[high]);
        while(low < high && nums[low] <= pivotkey)
            low++;
        swap(nums[low], nums[high]);
    }
    return low;
}
//快速排序
void quick_sort(vector<int> &nums, int low, int high)
{
    if(low < high)
    {
        int pivot = partition(nums, low, high);
        quick_sort(nums, low, pivot-1);
        quick_sort(nums, pivot+1, high);
    }
}

void max_heapify(vector<int> &nums, int cur, int end)
{
    //2 * cur + 1 为cur的第一个叶子节点
    for (int k = 2 * cur + 1; k < end; k = 2 * k + 1) {
        if (k + 1 < end && nums[k] < nums[k + 1]) {
            k++;
        }//两个叶子节点选择最大的
        if (nums[k] > nums[cur]) { //叶子节点比父节点大
            swap(nums[cur], nums[k]);
            cur = k;
        } else {
            break;
        }
    }
}
//堆排序
void heap_sort(vector<int> &nums)
{
    for (int i = nums.size() / 2 - 1; i >= 0; i--) { // build max heap
        max_heapify(nums, i, nums.size());
    }

    for (int i = nums.size() - 1; i > 0; i--) { // heap sort
        swap(nums[0],nums[i]);
        max_heapify(nums, 0, i);
    }
}

int main(void){
  int tmp[5] = {5,4,3,2,1};
  vector<int> num(tmp, tmp+5);
//  bubble_sort(num);
//  insert_sort(num);
//  selection_sort(num);
//  shell_sort(num);
//  merge_sort(num,0,num.size()-1);
//  quick_sort(num,0,num.size()-1);
  heap_sort(num);
  for(int i = 0; i < num.size(); ++i){
    cout << num[i] << endl;
  }
  return 0;
}

桶排序

• 首先求出最大值最小值，把此区间划分为k个区间（即k个桶），再分别对桶内元素进行排序，将桶内元素合并得到排序结果。
• 假设数据均匀分布，每个桶内元素为 n/k 个，并对桶内元素通过快排排序，每次排序复杂度为O(n/k log(n/k))，总的时间复杂度为O(n) + O(k)*O(n/k log(n/k))=O(n) + O(n log(n/k))，当k接近n时，复杂度可以认为是 O(n)
• 桶排序的复杂度与建桶的效果紧密相连，常见的建桶思路为将最大值最小值之间的区间平分,或桶的个数为 2^n,10^n
• 分治思想

基数排序

• 非比较算法
• 将所有待排整数统一为位数相同的整数（常见的为非负整数，对代码稍作修改，负整数也可通过基数排序进行排序）
• 从最低位或最高位开始一次进行稳定排序，完成之后整个序列即为一个有序序列

计数排序

• 以空间换时间
• 遍历数组统计每个数出现的次数，根据统计结果写回数组
• 是一种特殊的桶排序，当桶的个数最大时，桶排序即为计数排序

//sort
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
 
void bucketSort(vector<int> &arr){
	//将min和max等分成n份
	int low=999999999;
	int high=-999999999;
	for(int i=0;i<arr.size();i++){
		low=min(low,arr[i]);
		high=max(high,arr[i]);
	} 
	int size=(high-low)/10+1;  //一个桶的区间大小 
	vector<int> bucket[10];
	for(int i=0;i<arr.size();i++){
		int index=(arr[i]-low)/size;
		bucket[index].push_back(arr[i]); 
	}
	for(int i=0;i<10;i++){
		int bsize=bucket[i].size();
		sort(bucket[i].begin(),bucket[i].end());	
	}
	int index=0;
	for(int i=0;i<10;i++){
		for(int j=0;j<bucket[i].size();j++){
			arr[index]=bucket[i][j];
			index++;
		}
	}
}
 
//基数排序 
//从低位开始排序 
void redixSort(vector<int> &arr){
	int maxx=-999999999;
	for(int i=0;i<arr.size();i++){
		maxx=max(maxx,arr[i]);  //获取最大值 
	}
	int exp=10;
	while(maxx/exp!=0){
		exp*=10;  //获取最大值的位数 
	}
	vector<int> bucket[10]; 
	int exp2=10;
	while(exp2<=exp){
		for(int i=0;i<arr.size();i++){
			bucket[(arr[i]%exp2)/(exp2/10)].push_back(arr[i]); //放到对应的桶中 
		}
		int index=0;
		for(int i=0;i<10;i++){
			for(int j=0;j<bucket[i].size();j++){
				arr[index]=bucket[i][j];
				index++;
			}
			bucket[i].clear();    //因为桶是重复使用的，所以在一轮结束之后注意将桶清空 
		}
		exp2*=10;
	}
}
 
//考虑负数，从低位开始排序 
//将桶的大小扩展到20个即可 
void redixSortp(vector<int> &arr){
	int maxx=-999999999;
	for(int i=0;i<arr.size();i++){
		maxx=max(maxx,arr[i]);  //获取最大值 
	}
	int exp=10;
	while(maxx/exp!=0){
		exp*=10;  //获取最大值的位数 
	}
	vector<int> bucket[20];  
	int exp2=10;
	while(exp2<=exp){
		for(int i=0;i<arr.size();i++){
			bucket[(arr[i]%exp2)/(exp2/10)+10].push_back(arr[i]); //放到对应的桶中 
		}
		int index=0;
		for(int i=0;i<20;i++){
			for(int j=0;j<bucket[i].size();j++){
				arr[index]=bucket[i][j];
				index++;
			}
			bucket[i].clear();    //因为桶是重复使用的，所以在一轮结束之后注意将桶清空 
		}
		exp2*=10;
	}
}
 
void countSort(vector<int>& arr){
	int maxx=-999999999;
	int minn=999999999;
	for(int i=0;i<arr.size();i++){
		maxx=max(maxx,arr[i]);
		minn=min(minn,arr[i]);
	}
	int size=maxx-minn+1;
	int count[size]={0};
	for(int i=0;i<arr.size();i++){
		count[arr[i]-minn]++;
	}
	int index=0;
	for(int i=0;i<size;i++){
		for(int j=0;j<count[i];j++){
			arr[index]=i+minn;
			index++;
		}
	}
} 
 
int main(){
	int a[20]={45,95,23,78,21,2,5,0,-69,5,9,159,87,65,25,-56,56,56,57,100};
	vector<int> arr(a,a+20);
//	bucketSort(arr);
	redixSortp(arr);
//	countSort(arr);
	for(int i=0;i<20;i++){
		cout<<arr[i]<<" ";
	}
}

归并排序：

堆排序参考：

排序参考：

2、复杂度分析

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。 

3、场景

平均性能为O(nlogn)的有：快速排序，归并排序，希尔排序，堆排序。其中，快  排是最好的，其次是归并和希尔，堆排序在数据量很大时效果明显（堆排序适合处理大数据）。

大数据处理的一个例子：找出一千万个数中最小的前一百个数

思路：建立一百个节点的大顶堆，首先将前一百个数放入堆中，之后每放入一个数就删除一个堆顶元素，最后剩下的就是最小的一百个数。当然也可以分区处理，感兴趣的小伙伴可以网上搜一下大神们的帖子。

这四种排序可看作为“先进算法”，其中，快排效率最高（大数据就不行了，而且速度有概率性），但在待排序列基本有序的情况下，会变成冒泡排序，接近O(n^2).

希尔排序对增量的标准没有较为满意的答案，增量对性能会有影响。

归并排序效率非常不错，在数据规模较大的情况下，比希尔排序和堆排序要好。

 多数先进的算法都是因为跳跃式的比较，降低了比较次数，但牺牲了排序的稳定 性。

4、分类

1)插入排序法

    直接插入排序，希尔排序（面试最常问）

2)交换排序

    冒泡排序，快速排序（面试最常问）

3)选择排序

    直接选择排序，堆排序（面试最常问）

4)归并排序

    归并排序

5)基数排序