常用排序的使用

大耗子 2020年02月13日 322次浏览
  • 八大排序的理解

代码最简单,但效率低

冒泡:相邻比较思想

选择:选择最小的思想

代码简单,排序快速,常用

插入:与前面比较,大于自己,前移

希尔:在插入的基础上做出跨度

使用递归思想,排序快速,代码复杂

快速:在逻辑切分数组后将第一个元素作为参考值进行左右在切分,递归思想

归并:在逻辑切分数组后,进行回归原数组,需要辅助数组,递归思想

只能用于数字,代码复杂

基数:求余数得到同位数值得位置,回归原数组,直到比较完所有位数

计数:找到数组最大值,将所有数值进行排名,通过排名将数值导入辅助数组,在回归原数组,排名数组大小为最大值大小+1

  • 常用函数 
void Sort_swap(int& a,int &b)//数组元素交换
{
	int temp = a;
	a = b;
	b = temp;
}
void Sort_printf(int* arr,int len)//遍历打印
{
	for (int i = 0; i < len; i++)
		cout << arr[i] << "   "; 
	cout << endl;
}
bool Sort_check(int* arr, int len)//检查是否排序成功
{
	for (int i = 1; i < len; i++)
		if (arr[i] < arr[i - 1])
			return false;
	return true;
}
int getMax(int* arr, int len)//获取最大值
{
	int max = 0;
	for (int i = 0; i < len; i++)
	if (arr[i]>max)
		max = arr[i];
	return max;
}
int getTime(int max)//获取位数最大
{
	int i;
	for (i = 1; i < max / 10; i *= 10);
	return i;
}
  • 冒泡排序
void Sort_Bubble(int* arr, int len)
{
	printf("冒泡排序法\n");
	for (int i = 0; i < len-1; i++)
		for (int j = 0; j < len-1; j++)
			if (arr[j]>arr[j+1])
				Sort_swap(arr[j],arr[j+1]);
	//cout << Sort_check(arr, len) << endl;
}
  • 选择排序
void Sort_Select(int* arr, int len)
{
	printf("选择排序法\n");
	for (int i = 0; i < len - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		if (arr[min]>arr[j])//判断最小值并记录
			min = j;
		if (min != i)
			Sort_swap(arr[min], arr[i]);
	}
	//cout << Sort_check(arr, len) << endl;
}
  • 插入排序
void Sort_Insert(int* arr, int len)
{
	printf("插入排序法\n");
	for (int i = 1,j; i < len; i++)
	{
		int temp = arr[i];
		for (j = i-1; j >=0 && temp<arr[j] ; j--)//他的前一个数字大于temp就移动上去
			arr[j + 1] = arr[j];
		arr[j + 1] = temp;//移动停止后,放下数值
	}
//	cout << Sort_check(arr, len) << endl;
}
  • 希尔排序
void Sort_Shell(int* arr, int len)
{
	printf("希尔排序法\n");
	int jump = len >>1;//步长
	while (jump != 0)
	{
		for (int i = jump, j = 0, temp = 0; i < len; i++)
		{
			temp = arr[i];
			for (j = i - jump; j >= 0 && temp <arr[j]; j=j-jump)
				arr[j + jump] = arr[j];
			arr[j + jump] = temp;
		}
		jump >>= 1;
	}
	//cout << Sort_check(arr, len) << endl;
}
  • 快速排序
void Sort_Quick(int* arr, int low, int high)
{
	if (low >= high)
		return;
	int temp = arr[low];//中间参考值
	int b = low+1;//从第二个值开始,第一个值作为中间值
	int e = high;
	while (b <=e)
	{
		while (arr[b] <= temp && b <= e)//找到左边值大于参考值
			b++;
		while (arr[e] >= temp && b <= e)//找到右边值小于参考值
			e--;
		if (b<e)//位置相同和位置交叉不交换
		{
			Sort_swap(arr[b], arr[e]);//对应下表值交换
			b++;
			e--;
		}
	}
	arr[low] = arr[e];//所有大于参考值的左一个值
	arr[e] = temp;//参考值去到对应位置
	Sort_Quick(arr, low, e - 1);//分割
	Sort_Quick(arr, e + 1, high);
}
void Sort_Quick(int* arr, int len)
{
	printf("快速排序法\n");
	Sort_Quick(arr, 0, len - 1);
//	cout << Sort_check(arr, len) << endl;
}
  • 归并排序
void Sort_Merge(int* arr, int low, int mid,int hig)
{
	int lengh = hig - low + 1;
	int left = low;
	int right = mid + 1;
	int* temp=new int[lengh];
	for (int i = 0; i < lengh; i++)
	{
		if (left>mid)//左半部分数值用完
			temp[i] = arr[right++];
		else if (right > hig) // 右半部分数值用完
			temp[i] = arr[left++];
		else if (arr[right] < arr[left])//右值大于左值
			temp[i] = arr[right++];
		else
			temp[i] = arr[left++];
	}
	memmove(&arr[low], temp, sizeof(int)* lengh);//将排序好的数值返回到原数组
	delete[]temp;
	
}
void Sort_Merge(int* arr, int low, int hig)
{
	if (low >= hig)return;//停止递归条件
	int mid = (hig + low) >> 1;
	Sort_Merge(arr, low, mid);//拆分数组(在逻辑上拆分)
	Sort_Merge(arr, mid + 1, hig);
	Sort_Merge(arr, low, mid, hig);//合并数组
}
void Sort_Merge(int* arr, int len)
{
	printf("归并排序\n");
	Sort_Merge(arr, 0,  len-1);
	//cout << Sort_check(arr, len) << endl;
}
  • 基数排序
void Sort_Radix(int* arr, int len)
{
	printf("基数排序\n");
	int** temp = new int*[10];//申请动态数组并赋值
	for (int i = 0; i < 10; i++)
		temp[i] = new int[len];
	for (int n = 1, k = 0; n <= getTime(getMax(arr, len)); n *= 10, k = 0)
	{
		for (int i = 0; i < 10*len; i++)
			temp[i / len][i%len] = -1;//没有值得地方为-1

		for (int i = 0; i < len; i++)
			temp[arr[i] / n % 10][i] = arr[i];//第一个地方为余数  第二个为所在位置
		for (int i = 0; i < 10; i++)//将数值回倒进arr数组里
			for (int j = 0; j < len; j++)
				if (temp[i][j] != -1)
					arr[k++] = temp[i][j];	
	}
	for (int i = 0; i < 10; i++)//删除动态数组
		delete[]temp[i];
	delete[]temp;
	//cout << Sort_check(arr, len) << endl;
}
  • 计数排序
void Sort_Counting(int* arr, int len)
{
	printf("计数排序\n");
	int max = getMax(arr, len) + 1;//获取最大值,因为0也占一位所以+1
	int* temp = new int[len];//用来存arr数据
	int* rank = new int[max];//用来存储数字的排名信息
	memset(temp, 0, len * sizeof(int));//初始化数据
	memset(rank, 0, max * sizeof(int));
	for (int j = 0; j < len; j++) rank[arr[j]]++;//找到对应数字的位置
	for (int j = 1; j < max; j++) rank[j] += rank[j - 1];//开始存储排名
	for (int j = len - 1; j >= 0; j--)
	{
		temp[rank[arr[j]] - 1] = arr[j];//用排名来存储arr的数据
		rank[arr[j]]--;//存在相同数字,排名相同,需要-1
	}
	for (int i = 0; i < len; i++)
		arr[i] = temp[i];
	delete[]temp;
	delete[]rank;
//	cout << Sort_check(arr, len) << endl;
}

堆排序

//堆排序
void sink(int* arr, int k, int n)
{
	while (2 * k < n)//判断是否还有下堆
	{
		int j = 2 * k+1;//找到左子树
		if (j < n && arr[j]< arr[j + 1]) j++;//如果有右子树,比较左右子树取最大
		if (arr[k]>= arr[j]) break;//如果大于自己的子树则跳出
		Sort_swap(arr[k], arr[j]);//否则交换,形成堆
		k = j;//用来检测子树下面是否还有子树
	}
}
void Sort_Heap(int* arr, int len)
{
	printf("堆排序\n");
	if (Sort_check(arr, len))//如果已经排好就直接跳出 不用做最大堆
		return;
	int N = len-1;//作为堆末尾下标
	for (int k = (N) / 2 - 1; k >= 0; k--)//将数组做成一个堆
		sink(arr, k, N);
	while (N>0)
	{
		Sort_swap(arr[0], arr[N--]);//最大值交换到末尾,末尾指向下标-1
		sink(arr, 0, N);//将交换上来的值下沉
	}
	//Sort_printf(arr, len);
	//cout << Sort_check(arr, len) << endl;
}

测试代码

#define LEN 20
#include <time.h>
void main()
{
	int arr[LEN] = { 4, 2, 6, 8, 9, 3, 1, 10, 5, 7 };
	int arr1[LEN];
	//int arr2[LEN];
	//int arr3[LEN];
	//int arr4[LEN];
	//int arr5[LEN];
	//int arr6[LEN];
	//int arr7[LEN];
	//int arr8[LEN];
	//int arr9[LEN];
	srand((unsigned)time(NULL));
	for (int i = 0; i < LEN; i++)
	{
		arr[i] = rand() % 100;
		arr1[i] = arr[i];
		//arr2[i] = arr[i];
		//arr3[i] = arr[i];
		//arr4[i] = arr[i];
		//arr5[i] = arr[i];
		//arr6[i] = arr[i];
		//arr7[i] = arr[i];
		//arr8[i] = arr[i];
		//arr9[i] = arr[i];
	}
	
	int len = sizeof(arr) / sizeof(arr[0]);
	Sort_printf(arr1, len);
	clock_t start_time = clock();
	Sort_Bubble(arr1, len);
	clock_t end_time = clock();
	cout << end_time-start_time <<"ms"<< endl;
	Sort_printf(arr1, len);

	//start_time = clock();
	//Sort_Select(arr2, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Insert(arr3, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Shell(arr4, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Quick(arr5, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Merge(arr6, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Radix(arr7, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Counting(arr8, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;

	//start_time = clock();
	//Sort_Heap(arr9, len);
	//end_time = clock();
	//cout << end_time - start_time << "ms" << endl;
}
  • 测试

个人测试结果,不同数据,不同电脑可能会出现不同结果

测试数据是通过随机数种子取到的28000个数据