[数据结构与算法]自学笔记----------------十大排序算法（C++版）

序言：swap函数的源代码

template<class T>
void swap(T &a,T &b){
	T temp = a;
	a = b;
	b =temp;
}

一、冒泡排序

算法：
1、比较相邻的元素，如果前一个大于后一个，则交换这两个数。
2、比较每一对相邻元素，从开始的第一对到最后一对
例： 3 5 2 4 1 6 -> 3 5 2 4 1 6 -> 3 2 5 4 1 6 -> 3 2 4 5 1 6 -> 3 2 4 1 5 6 -> 3 2 4 1 5 6
平均时间复杂度： O(N2)
空间复杂度： O(1)
稳定

冒泡次数        冒泡结果       交换轮数     检查轮数
原始数据      4 5 6 3 2 1        0       
第1次冒泡     4 5 3 2 1 6        3         5
第2次冒泡     4 3 2 1 5 6        3         4
第3次冒泡     3 2 1 4 5 6        3         3
第4次冒泡     2 1 3 4 5 6        2         2
第5次冒泡     1 2 3 4 5 6        1         1

代码实现：

//冒泡排序
void bubbleSort(vector<int>&nums) {
	
	int n = nums.size();
	if (n <= 1) return;
	bool flag = false;
	//下标从0开始  但是从下标1开始交换
	for (int i = 1; i < n ; i++) {
		//1 2 3 4 5 ... n-1     有n-1个数可与下一个数交换
		//i= 1  j= 1,2,...n-1   i之前的数不需要交换，i之后的交换
		for (int j = 1; j < n - i + 1; j++) {
			
			if (nums[j] < nums[j - 1]) {
				swap(nums[j], nums[j - 1]);
				flag = true;  //表示有数据交换
			}
		}
		if (!flag) break;   //没有数据交集，提前退出
	}
}

二、选择排序

算法：
每次从未排序的区间区间中找到最小的元素，将其放到已排序区间的末尾
平均时间复杂度： O(N2)
空间复杂度： O(1)
不稳定

//选择排序
void selectSort(vector<int>&nums) {
	int n = nums.size();
	if (n <= 1) return;
	//快慢指针
	for (int i = 0; i < n - 1; i++) {
		int tmp = i;
		for (int j = i + 1; j < n; j++) {
			if (nums[j] < nums[tmp])   tmp = j; //找出最小数的下标
		}
		swap(nums[tmp], nums[i]);
	}
}

三、插入排序

算法：
从数组第一个元素开始（初始已排序区间只有一个元素），遍历未排序的每一个元素，插入到已排序的区间保证数据有序。
平均时间复杂度： O(N2)
空间复杂度： O(1)
稳定

代码实现：

//插入排序
void insertSort(vector<int>&nums) {
	int n = nums.size();
	if (n <= 1) return;
	//双指针  对已排序的数进行插入
	for (int i = 0; i < n; i++) {
		for (int j = i; j > 0; j--) {
			if (nums[j] < nums[j - 1]) {	
				swap(nums[j], nums[j - 1]);
			}
		}
	}
}

四、希尔排序

算法：
将比较的全部元素取越来越小的步长，分几个区域排序
平均时间复杂度： O(Nlog2N)
空间复杂度： O(1)
不稳定

//希尔排序
void shellSort(vector<int>&nums) {
	int n = nums.size();
	if (n <= 1) return;
	//取步长
	for (int gap = n / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < n; i++) {
			for (int j = i; j - gap >= 0; j -= gap) {
				if (nums[j] < nums[j - gap]) {
					swap(nums[j - gap], nums[j]);
				}
			}
		}
	}
}

五、归并排序

算法：
将全部元素分半分组，每一组再分半分组，递归下去，两两比较，再逐步合并到临时数组，最后全部排序
平均时间复杂度： O(NlogN)
空间复杂度： O(N)
稳定

//归并排序
void merge(vector<int>&nums, int left, int mid, int right) {
	int n = nums.size();
	//临时数组 必须规定容量n
	vector<int>temp(n);
	int i = left, j = mid + 1;//被分割的两个数组的起点下标
	int k = 0;//临时数组的下标
	while(i <= mid && j <= right) {
		if (nums[i] < nums[j])  temp[k++] = nums[i++];
		else temp[k++] = nums[j++];
	}
	//将剩余数据全部放入
	while (i <= mid) temp[k++] = nums[i++];
	while (j <= right) temp[k++] = nums[j++];


	//将临时数组中元素全部拷贝回原数组   
	for (int m = 0; m < k; m++) nums[left + m] = temp[m];

}
void mergeSort(vector<int>&nums,int left,int right) {
	if (left >= right) return;
	int mid = left + (right - left) / 2;

	//分治 递归
	mergeSort(nums, left, mid);
	mergeSort(nums, mid + 1, right);

	merge(nums, left, mid, right);//合并
}

六、快速排序

算法：
确定一个枢纽pivot，将所有其他元素跟pivot比较，较小的在前，较大的在后
平均时间复杂度： O(NlogN)
空间复杂度： O(logN)
不稳定

//快速排序
void quickSort(vector<int>&nums, int left, int right) {
	if (left >= right) return;
	
	//双指针
	int i = left, j = right;
	int pivot = nums[i];
	while (i < j) {
		//右指针 从右往左  小于pivot的值放左边
		while (i < j&&nums[j] >= pivot) j--;
		nums[i] = nums[j];
		//左指针 从左往右  大于pivot的值放右边
		while (i < j&&nums[i] <= pivot) i++;
		nums[j] = nums[i];
	}
	//更新
	nums[i] = pivot;
	//以nums[i]为界  分治  递归
	quickSort(nums, left, i - 1);
	quickSort(nums, i + 1, right);
}

七、堆排序

算法：
利用大根堆或小根堆的特性
ps:一般用到堆排序的算法，只需要priority_queue实现即可，这里不讨论堆排序本身实现的算法，讨论一下利用堆的特性实现排序的方法。
平均时间复杂度： O(NlogN)
空间复杂度： O(1)
不稳定

定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆

1.基本类型

//对于基础类型 默认是大顶堆
    priority_queue<int> a; 
    //等同于 priority_queue<int, vector<int>, less<int> > a;
     priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆

2.pair的比较，先比较第一个元素，第一个相等比较第二个

priority_queue<pair<int, int> > a;

3.自定义类型

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};
priority_queue<tmp1> d;
priority_queue<tmp1, vector<tmp1>, tmp2> f;

八、计数排序

算法：
用待排序的数作为计数组的下标，统计每个数字的个数
平均时间复杂度： O(N2)
空间复杂度： O(1)
稳定

//计数排序
void countSort(vector<int>&nums) {
	int n = nums.size();
	if (n <= 1) return;

	int maxValue = nums[0];
	//找出最大值
	for (int i = 1; i < n; i++) {
		maxValue = max(maxValue, nums[i]);
	}

	//哈希表
	vector<int>tmp1(n + 1);
	for (int i = 0; i < n; i++) {
		tmp1[nums[i]]++;//统计每个数字的个数
	}
	//将所有数字分为 1~maxValue
	for (int i = 1; i <= maxValue; i++) {
		tmp1[i] += tmp1[i - 1];
	}
	vector<int>tmp2(n + 1);
	for (int i = n - 1; i >= 0; i--) {
		int idx = tmp1[nums[i]] - 1;
		tmp2[idx] = nums[i];
		tmp1[nums[i]]--;
	}

	for (int i = 0; i < n; i++) {
		nums[i] = tmp2[i];
	}
}

九、桶排序

算法：
将数组分到有限数量的桶里，每个桶再分别排序(个人理解，找出最大或者最小元素后，以序号的方式放桶，主要存储相同元素，最后大小输出直接按照序号输出)
平均时间复杂度： O(N+K)
空间复杂度： O(N+K)
稳定

//桶排序
void bucketSort(vector<int>&nums) {
	int len = nums.size();
	if (len <= 1) return;

	int low = *min_element(nums.begin(), nums.end());//最小元素
	int high = *max_element(nums.begin(), nums.end());//最大元素
	int n = high - low + 1;
	vector<int>buckets(n);//放置的桶
	vector<int>ans;

	for (auto x : nums) buckets[x - low]++;//相同的数放一个桶
	//按照序号输出
	for (int i = 0; i < n; i++) {
		//将相同的数输出
		for (int j = 0; j < buckets[i]; j++) {
			ans.push_back(i + low);
		}
	}
	for (int i = 0; i < ans.size(); i++) {
		nums[i] = ans[i];
	}
}

十、基数排序

算法：
对排序的数据有要求，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a的高位>b的高位，则a>b。此外，每一位的数据范围不能太大，需要一定线性，基数排序相当于循环多次实现多次桶排序。
ps:由于对数据有要求，加上时间空间复杂度并没有优于桶排序，这里不作深入研究。
平均时间复杂度： O(N×K)
空间复杂度： O(N+K)
稳定