排序算法

一、冒泡排序

/*
* 冒泡排序
* 比较交换相邻元素
* 思路简单，仅学习用
*/
class Bubble
{
public:
	void mysort(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;
				}
			}
		}
	}
};
int main()
{
vector<int> nums = {9, 7, 5, 3, 1, 0, 8, 4, 6, 2};
Bubble bubble;
bubble.mysort(nums);
for (int num : nums)
{
cout << num << " ";
}
return 0;
}

二、选择排序

/*
* 选择排序
* 思路：找最小元素，放到最终位置
* 特点：时间：O(n²)、非稳定排序
* 适用：数据量少
*/
class Select
{
public:
	void mysort(vector<int> &nums)
	{
		int n = nums.size();
		for (int i = 0; i < n - 1; i++)
		{
		int minPos = i;
			for (int j = i + 1; j < n; j++)
			{
				if (nums[j] < nums[minPos])  //记录最小的元素的下标赋值给minPos,并将其移动到i
				{
				minPos = j;
				}
			}
		int temp = nums[i];
		nums[i] = nums[minPos];
		nums[minPos] = temp;
		}
	}
};
int main()
{
vector<int> nums = {9, 7, 5, 3, 1, 0, 8, 4, 6, 2};
Select select;
select.mysort(nums);
for (int num : nums)
{
cout << num << " ";
}
return 0;
}

三、插入排序

/*
* 插入排序
* 思路：抓牌一样，插入当前手牌中的适当位置
* 特点：时间：O(n²)
* 适用：基本有序
*/
class Insert
{
public:
	void mysort(vector<int> &nums)
	{
	int n = nums.size();
		for (int i = 1; i < n; i++)
		{
		int pos = i - 1;
		int cur = nums[i];
		while (pos >= 0 && cur < nums[pos]) //维护所有i前面的元素的顺序
		{
		nums[pos + 1] = nums[pos];
		pos--;
		}
		nums[pos + 1] = cur;
		}
	}
};
int main()
{
vector<int> nums = {9, 7, 5, 3, 1, 0, 8, 4, 6, 2};
Insert insert;
insert.mysort(nums);
for (int num : nums)
{
cout << num << " ";
}
return 0;
}

四、希尔排序

/*https://www.runoob.com/datastructures/shellsort.html
* 希尔排序
* 思路：间隔分组+自定义排序（这里给出的是冒泡）
* 特点：时间：O(nlogn)、非稳定排序
* 适用：数据量大
*/
class Shell
{
public:
	void mysort(vector<int> &nums)
	{
		int n = nums.size();
		int gap = n / 2;
		while (gap > 0)
		{
			for (int j = gap; j < n; j++)
			{
				int i = j;
				while (i >= gap && nums[i] < nums[i - gap]) //注意这里用while
				{
					int temp = nums[i];
					nums[i] = nums[i - gap];
					nums[i - gap] = temp;
					i -= gap;
				}
			}
		gap /= 2;
		}
	}
};
int main()
{
vector<int> nums = {9, 7, 5, 3, 1, 0, 8, 4, 6, 2};
Shell shell;
shell.mysort(nums);
for (int num : nums)
{
cout << num << " ";
}
return 0;
}

五、归并排序

/*
* 归并排序
* 思路：递归思想
* 特点：时间：O(nlogn)、空间：O(n)——非原地
* 适用：不受数据影响，所需空间与n成正比
*/
#include <vector>
#include <iostream>
using std::vector;
using std::cout;

class Merge
{
public:
	void mysort(vector<int> &nums, int left, int right)
	{
		if (left < right)
		{
		int mid = left + (right - left) / 2;
		mysort(nums, left, mid);
		mysort(nums, mid + 1, right);
		merge(nums, left, right);
		}
	return;
	}
	void merge(vector<int> &nums, int left, int right)
	{
	vector<int> temp(nums.size());	//temp用来存储临时数组，将数组一分为二，先把小的放在temp中，有点递归的意思
	int mid = left + (right - left) / 2;
	int p = left;
	int q = mid + 1;
	int k = left;
	while (p <= mid && q <= right)
		{
			if (nums[p] < nums[q])
			temp[k++] = nums[p++];
			else
			temp[k++] = nums[q++];
		}
	while (p <= mid)
	temp[k++] = nums[p++];
	while (q <= right)
	temp[k++] = nums[q++];
	for (int i = left; i <= right; i++)
	nums[i] = temp[i];
	}
};
int main()
{
vector<int> nums = {9, 7, 5, 3, 1, 0, 8, 4, 6, 2};
Merge merge;
merge.mysort(nums, 0, nums.size() - 1);
for (int num : nums)
cout << num << " ";
return 0;
}

六、快速排序

//快速排序
#include <iostream> 
using namespace std;
void QuickSort(int *array,int low,int high){	//快排 
	if(low>=high){	//若待排序序列只有一个元素，返回空 
		return ;
	}
	int i=low;	//i作为指针从左向右扫描 
	int j=high;	//j作为指针从右向左扫描
	int key=array[low];//第一个数作为基准数 
	while(i<j){
		while(array[j]>=key&&i<j){	//从右边找小于基准数的元素 （此处由于j值可能会变，所以仍需判断i是否小于j） 
			j--;	//找不到则j减一 
		}
		array[i]=array[j];	//找到则赋值 
		while(array[i]<=key&&i<j){	//从左边找大于基准数的元素 
			i++;	//找不到则i加一 
		}
		array[j]=array[i];	//找到则赋值 
	}
	array[i]=key;	//当i和j相遇，将基准元素赋值到指针i处 
	QuickSort(array,low,i-1);	//i左边的序列继续递归调用快排 
	QuickSort(array,i+1,high);	//i右边的序列继续递归调用快排 
}
int main(){
	int array[]={49,38,65,97,76,13,27,49};
	int length=sizeof(array)/sizeof(*array);
	cout<<"原始序列：";
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
	QuickSort(array,0,length-1);
	cout<<"快排序列：";
	for(int i=0;i<length;i++){
		cout<<array[i]<<" ";
	}
	return 0;
}