8大常用排序写法

54 阅读 0 评论 36 点赞

我是靠谱客的博主超帅金鱼，最近开发中收集的这篇文章主要介绍8大常用排序写法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

八大排序的理解

个人对八大排序的理解,如有错误请指出

新人第一次写博客,排版可能稍微不好看,请谅解

代码最简单,但效率低

冒泡：相邻比较思想

选择：选择最小的思想

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

插入：与前面比较，大于自己，前移

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

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

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

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

只能用于数字,代码复杂

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

计数：找到数组最大值，将所有数值进行排名，通过排名将数值导入辅助数组，在回归原数组，排名数组大小为最大值大小+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;
}