C++常用排序算法汇总
清泛原创
1、选择排序(SelectSort)
更多请移步至：排序(Sort)
/************************************
* 简单选择排序
* 稳定排序，O{n^2} ~ O{n^2}
* 从首位开始，循环一次找出一个比首位小的值，交换
*
* https://www.tsingfun.com
************************************/
#include<stdio.h>
#include<stdlib.h>
/*
第一种形式的选择排序
选择排序后的顺序为从小到大
*/
void Select_Sort1(int *arr,int len)
{
int i,j;
for(i=0;i<len;i++)
for(j=i+1;j<len;j++)
if(arr[i] > arr[j])
{
int exchange = arr[i];
arr[i] = arr[j];
arr[j] = exchange;
}
}
/*
第二种形式的选择排序，减少了元素互换的操作
选择排序后的顺序为从小到大
*/
void Select_Sort2(int *arr,int len)
{
int i,j,min;
for(i=0;i<len;i++)
{
min = i; //用来记录每一趟比较的最小值的位置
for(j=i+1;j<len;j++)
if(arr[min] > arr[j])
min = j; //仅记录最小值的位置
//如果最小值的位置发生了变化，
//则最后执行一次元素互换的操作
if(min != i)
{
int exchange = arr[i];
arr[i] = arr[min];
arr[min] = exchange;
}
}
}
int main()
{
int num;
printf("请输入排序的元素的个数：");
scanf("%d",&num);
int i;
int *arr = (int *)malloc(num*sizeof(int));
printf("请依次输入这%d个元素（必须为整数）：",num);
for(i=0;i<num;i++)
scanf("%d",arr+i);
printf("插入排序后的顺序：");
Select_Sort2(arr,num);
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
free(arr);
arr = 0;
return 0;
}
2、冒泡排序(BubbleSort)
/************************************
* 冒泡排序
* 稳定排序，O{n} ~ O{n^2}
* 从末尾开始，与上个元素比较并交换
* 每轮都将能最小的元素换到首位
*
* https://www.tsingfun.com
************************************/
#include<stdio.h>
#include<stdlib.h>
/*
冒泡排序后的顺序为从小到大
*/
void Bubble_Sort(int *arr,int len)
{
int i,j,exchange;
for(i=0;i<len-1;i++)
for(j=0;j<len-i-1;j++)
if(arr[j] > arr[j+1])
{
exchange = arr[j];
arr[j] = arr[j+1];
arr[j+1] = exchange;
}
}
int main()
{
int num;
printf("请输入排序的元素的个数：");
scanf("%d",&num);
int i;
int *arr = (int *)malloc(num*sizeof(int));
printf("请依次输入这%d个元素（必须为整数）：",num);
for(i=0;i<num;i++)
scanf("%d",arr+i);
printf("冒泡排序后的顺序：");
Bubble_Sort(arr,num);
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
free(arr);
arr = 0;
return 0;
}
3、快速排序(QuickSort)
/************************************
* 快速排序
* 不稳定排序，O{nlogn} ~ O{n^2}
* 适合排序大量数据
* 设最左边为基准数
* 右边往左找一个比基准数小的
* 左边往右找一个比基准数大的，和上一步交换
* 碰头后和基准数交换
*
* https://www.tsingfun.com
************************************/
#include <iostream>
void printArray(int *array, int n)
{
for (int i = 0; i < n; ++i)
std::cout << array[i] << std::endl;
}
void quickSort(int *array, int low, int high)
{
int i = low;
int j = high;
int pivot = array[(i + j) / 2];
int temp;
while (i <= j)
{
while (array[i] < pivot)
i++;
while (array[j] > pivot)
j--;
if (i <= j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (j > low)
quickSort(array, low, j);
if (i < high)
quickSort(array, i, high);
}
int main()
{
int array[] = {95, 45, 48, 98, 1, 485, 65, 478, 1, 2325};
int n = sizeof(array)/sizeof(array[0]);
std::cout << "Before Quick Sort :" << std::endl;
printArray(array, n);
quickSort(array, 0, n-1);
std::cout << "After Quick Sort :" << std::endl;
printArray(array, n);
return (0);
}
4、归并排序(MergeSort)
/************************************
* 归并排序
* 稳定排序，O{nlogn} ~ O{nlogn}
* 稳定排序中最高效的
* 倒置的二叉树，两两排序后合并
*
* https://www.tsingfun.com
************************************/
#include<stdio.h>
#include<stdlib.h>
/*
将有序的arr[start...mid]和有序的arr[mid+1...end]归并为有序的brr[0...end-start+1],
而后再将brr[0...end-start+1]复制到arr[start...end]，使arr[start...end]有序
*/
void Merge(int *arr,int *brr,int start,int mid,int end)
{
int i = start;
int j = mid+1;
int k = 0;
//比较两个有序序列中的元素，将较小的元素插入到brr中
while(i<=mid && j<=end)
{
if(arr[i]<=arr[j])
brr[k++] = arr[i++];
else
brr[k++] = arr[j++];
}
//将arr序列中剩余的元素复制到brr中
//这两个语句只可能执行其中一个
while(i<=mid)
brr[k++] = arr[i++];
while(j<=end)
brr[k++] = arr[j++];
//将brr中的元素复制到arr中，使arr[start...end]有序
for(i=0;i<k;i++)
arr[i+start] = brr[i];
}
/*
借助brr数组对arr[start...end]内的元素进行归并排序
归并排序后的顺序为从小到大
*/
void MSort(int *arr,int *brr,int start,int end)
{
if(start < end)
{
int mid = (start+end)/2;
MSort(arr,brr,start,mid); //左边递归排序
MSort(arr,brr,mid+1,end); //右边递归排序
Merge(arr,brr,start,mid,end); //左右序列归并
}
}
/*
将该排序算法封装起来
*/
void Merge_Sort(int *arr,int len)
{
int *brr = (int *)malloc(len*sizeof(int));
MSort(arr,brr,0,len-1);
free(brr);
brr = 0;
}
int main()
{
int num;
printf("请输入排序的元素的个数：");
scanf("%d",&num);
int i;
int *arr = (int *)malloc(num*sizeof(int));
printf("请依次输入这%d个元素（必须为整数）：",num);
for(i=0;i<num;i++)
scanf("%d",arr+i);
printf("归并排序后的顺序：");
Merge_Sort(arr,num);
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
free(arr);
arr = 0;
return 0;
}
5、堆排序(HeapSort)
/************************************
* 堆排序
* 不稳定排序，O{nlogn} ~ O{nlogn}
* 将数组转化为完全二叉树
* 父节点比左右子节点都大的称为大根堆，都小的称为小根堆
* 从后往前遍历所有非叶子节点，初始化大根堆
* 将堆顶和最后一个元素交换，得到一个最大值
* 通过不断的调整大根堆，得到排序后的数组
*
* https://www.tsingfun.com
************************************/
#include<stdio.h>
#include<stdlib.h>
/*
arr[start+1...end]满足最大堆的定义，
将arr[start]加入到最大堆arr[start+1...end]中，
调整arr[start]的位置，使arr[start...end]也成为最大堆
注：由于数组从0开始计算序号，也就是二叉堆的根节点序号为0，
因此序号为i的左右子节点的序号分别为2i+1和2i+2
*/
void HeapAdjustDown(int *arr,int start,int end)
{
int temp = arr[start]; //保存当前节点
int i = 2*start+1; //该节点的左孩子在数组中的位置序号
while(i<=end)
{
//找出左右孩子中最大的那个
if(i+1<=end && arr[i+1]>arr[i])
i++;
//如果符合堆的定义，则不用调整位置
if(arr[i]<=temp)
break;
//最大的子节点向上移动，替换掉其父节点
arr[start] = arr[i];
start = i;
i = 2*start+1;
}
arr[start] = temp;
}
/*
堆排序后的顺序为从小到大
因此需要建立最大堆
*/
void Heap_Sort(int *arr,int len)
{
int i;
//把数组建成为最大堆
//第一个非叶子节点的位置序号为len/2-1
for(i=len/2-1
;i>=0;i--)
HeapAdjustDown(arr,i,len-1);
//进行堆排序
for(i=len-1;i>0;i--)
{
//堆顶元素和最后一个元素交换位置，
//这样最后的一个位置保存的是最大的数，
//每次循环依次将次大的数值在放进其前面一个位置，
//这样得到的顺序就是从小到大
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//将arr[0...i-1]重新调整为最大堆
HeapAdjustDown(arr,0,i-1);
}
}
int main()
{
int num;
printf("请输入排序的元素的个数：");
scanf("%d",&num);
int i;
int *arr = (int *)malloc(num*sizeof(int));
printf("请依次输入这%d个元素（必须为整数）：",num);
for(i=0;i<num;i++)
scanf("%d",arr+i);
printf("堆排序后的顺序：");
Heap_Sort(arr,num);
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
free(arr);
arr = 0;
return 0;
}
6、插入排序(InsertSort)
/************************************
* 直接插入排序
* 稳定排序，O{n} ~ O{n^2}
* 循环找出一个右边比左边小的值作为哨兵
* 向左查找所有大于哨兵的值，右移
* 然后将哨兵插入空出的一个位置
*
* https://www.tsingfun.com
************************************/
#include<stdio.h>
#include<stdlib.h>
/*
第一种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort1(int *arr,int len)
{
int i;
//从第1个元素开始循环执行插入排序
for(i=1;i<len;i++)
{ //将第i个元素分别与前面的元素比较，插入适当的位置
int key = arr[i];
if(key<arr[i-1])
{ //一直向左进行比较，直到插入到适当的位置
int count = 0; //用来记录key在与前面元素时向左移动的位置
while(i>0 && key<arr[i-1])
{
arr[i] = arr[i-1];
arr[i-1] = key;
i--;
count++;
}
//将待插入的数定位到下一个元素，
//因为后面还要执行i++，所以这里不再加1
i += count;
}
}
}
/*
第二种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort2(int *arr,int len)
{
int i,j;
for(i=1;i<len;i++)
if(arr[i] < arr[i-1])
{ //向前逐个比较，直到需要插入的地方
int key = arr[i];
for(j=i-1;j>=0 && arr[j]>key;j--)
arr[j+1] = arr[j];
arr[j+1] = key; //插入key
}
}
/*
第三种代码形式
插入排序后的顺序为从小到大
*/
void Insert_Sort3(int *arr,int len)
{
int i,j;
for(i=1;i<len;i++)
for(j=i-1;j>=0 && arr[j]>arr[j+1];j--)
{
//交换元素数值
//由于arr[j]不等于arr[j+1]，
//因此可以安全地用该交换方法
arr[j]^=arr[j+1];
arr[j+1]^=arr[j];
arr[j]^=arr[j+1];
}
}
int main()
{
int num;
printf("请输入排序的元素的个数：");
scanf("%d",&num);
int i;
int *arr = (int *)malloc(num*sizeof(int));
printf("请依次输入这%d个元素（必须为整数）：",num);
for(i=0;i<num;i++)
scanf("%d",arr+i);
printf("插入排序后的顺序：");
// Insert_Sort1(arr,num);
// Insert_Sort2(arr,num);
Insert_Sort3(arr,num);
for(i=0;i<num;i++)
printf("%d ",arr[i]);
printf("\n");
free(arr);
arr = 0;
return 0;
}
上一篇：Linux C++ 单元测试与gcov代码覆盖率统计
下一篇：C++简练易用的线程池(threadpool)及上下文隔离的无锁线程池(isolated_threadpool)完整实现
评论加载中，请稍后...