简介本文介绍C++实现C++实现8种排序算法，主要包括冒泡排序、插入排序、二分插入排序、希尔排序、直接选择排序、堆排序、归并排序、快速排序，直接上代码，感兴趣的朋友可以参考一下。
/////////////////////////////////////////////
//
// 冒泡排序 v1.0
// arr 整型数组指针
// n 数组长度
/////////////////////////////////////////////
template <class T>
void BubbleSort(T* arr, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n - 1 - i; ++j)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}/////////////////////////////////////////////
//
// 冒泡排序 v2.0
// arr 整型数组指针
// n 数组长度
/////////////////////////////////////////////
template <class T>
void BubbleSort(T* arr, int n)
{
int bFlag = false;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n - 1 - i; ++j)
{
// 交换数据
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
bFlag = true;
}
}
if (bFlag == false) // 无交换直接跳出
{
break;
}
}
}备注：对于最坏情况，该改进和未改进差不多。
/////////////////////////////////////////////
//
// 直接插入排序
// 基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
// a int* 整型数组指针
// N int 数组长度
/////////////////////////////////////////////
void InsertSort(int *a, int N)
{
int i = 0;
int j = 0;
for (int i = 1; i < N; i++)
if (a[i] < a[i - 1])
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j]; // 把比temp大或相等的元素全部往后移动一个位置
a[j + 1] = temp;
}
}
/////////////////////////////////////////////
//
// 二分插入排序
// 基本思想：基于插入排序，在查找插入位置时采用二分查找法。
// A int* 整型数组指针
// length int 数组长度
/////////////////////////////////////////////
void BinInsertSort(int* A, int length)
{
int middle = 0;
int left = 0;
int right = 0;
for (int i = 1; i<length; i++) // 从第2个元素开始
{
int insertNum = A[i];
// 将有序区作为查找范围
left = 0;
right = i - 1;
// 二分查找
while (left <= right)
{
// 依次取查找范围的中间位置
middle = (left + right) / 2;
if (insertNum<A[middle])
right = middle - 1;// 在前半区查找
else
left = middle + 1; // 在后半区查找
}
// 移动元素, 空出要插入的位置
for (int j = i - 1; j >= left; j--)
A[j + 1] = A[j];
// 将当前元素插入适当位置
A[left] = insertNum;
}
}/////////////////////////////////////////////
//
// 希尔排序
// a 整型数组指针
// n 数组长度
/////////////////////////////////////////////
void ShellSort(int* a, int n)
{
int i = 0;
int j = 0;
int x = 0;
int gap = n / 2;
while (gap >= 1) // 循环至增量为1时结束
{
for (i = gap; i<n; i++)
{
x = a[i]; // 获取序列中的下一个数据
j = i - gap; // 序列中前一个数据的序号
while (j >= 0 && a[j]>x) // 下一个数大于前一个数
{
a[j + gap] = a[j]; // 将后一个数向前移动
j = j - gap; // 修改序号，继续向前比较
}
a[j + gap] = x; // 保存数据
}
gap /= 2; // 缩小增量
}
}
/////////////////////////////////////////////
//
// 直接选择排序
// a 整型数组指针
// n 数组长度
/////////////////////////////////////////////
void SelectSort(int* a, int n)
{
int i, j, t, k;
for (i = 0; i<n - 1; i++)
{
k = i;
for (j = i + 1; j<n; j++)
if (a[k]>a[j]) k = j;
t = a[i];
a[i] = a[k];
a[k] = t;
}
}直接选择排序适合在移动成本高，比较成本低的场景。
不稳定，元素的位置可能会改变。
void HeapAdjust(int a[],int s,int n)//构成堆
{
int j,t;
while(2*s+1<n) //第s个结点有右子树
{
j=2*s+1 ;
if((j+1)<n)
{
if(a[j]<a[j+1])//右左子树小于右子树，则需要比较右子树
j++; //序号增加1，指向右子树
}
if(a[s]<a[j])//比较s与j为序号的数据
{
t=a[s]; //交换数据
a[s]=a[j];
a[j]=t;
s=j ;//堆被破坏，需要重新调整
}
else //比较左右孩子均大则堆未破坏，不再需要调整
break;
}
}
void HeapSort(int a[],int n)//堆排序
{
int t,i;
int j;
for(i=n/2-1;i>=0;i--) //将a[0,n-1]建成大根堆
HeapAdjust(a, i, n);
for(i=n-1;i>0;i--)
{
t=a[0];//与第i个记录交换
a[0] =a[i];
a[i] =t;
HeapAdjust(a,0,i); //将a[0]至a[i]重新调整为堆
}
}void MergeStep(int a[],int r[],int s,int m,int n) //相邻有序段合并
{
int i,j,k;
k=s;
i=s;
j=m+1;
while(i<=m && j<=n) //当两个有序表都未结束时，循环比较
{
if(a[i]<=a[j]) //当较小的元素复制到R中
r[k++]=a[i++];
else
r[k++]=a[j++];
}
while(i<=m) //将未合并的部分复制到R中
r[k++]=a[i++];
while(j<=n)
r[k++]=a[j++]; //将未合并的部分复制到R中
}
void MergePass(int a[],int r[],int n,int len) //完成一遍合并的函数
{
int s,e;
s=0;
while(s+len<n) //至少有两个有序段
{
e=s+2*len-1;
if(e>=n) //最后一段可能少于len个结点
e=n-1;
MergeStep(a,r,s,s+len-1,e); //相邻有序段合并
s=e+1; //下一对有序段中左段的开始下标
}
if(s<n) //还剩一个有序段，将其从A中复制到R中
for(;s<n;s++)
r[s]=a[s];
}
void MergeSort(int a[],int n)
{
int *p;
int len=1; //有序序列的长度
int f=0; //变量f作标志
if(!(p=(int *)malloc(sizeof(int)*n))) //分配内存空间，保存临时数据
{
printf("分配临时内存失败!\n");
exit(0);
}
while(len<n)
{
if(f) //交替地在A和P之间来回合并
MergePass(p,a,n,len); //调用MergePass，对p合并到a
else
MergePass(a,p,n,len); //调用MergePass，对a合并到p
len*=2; //增加有序序列长度
f=1-f; //使f值在0和1之间切换
}
if(f) //若进行了排序
for(f=0;f<n;f++) //将数组p中的数据复制到数组a
a[f]=p[f];
free(p); //释放分配的内存
}int Division(int a[],int left, int right) //分割
{
int base=a[left]; //基准元素
while(left<right)
{
while(left<right && a[right]>base)
--right; //从右向左找第一个比基准小的元素
a[left]=a[right];
while(left<right && a[left]<base )
++left; //从左向右找第一个比基准大的元素
a[right]=a[left];
}
a[left]=base;
return left;
}
void QuickSort(int a[],int left,int right)
{
int i,j;
if(left<right)
{
i=Division(a,left,right); //分割
QuickSort(a,left,i-1); //将两部分分别排序
QuickSort(a,i+1,right);
}
}#include <ctime>
#include <iostream>
using namespace std;
/////////////////////////////////////////////
//
// 获取随机数
// min 最小值
// max 最大值
/////////////////////////////////////////////
int GetRandom(int min, int max)
{
return (rand() % static_cast<int>(max + 1 - min)) + min;
}
int _tmain(int argc, _TCHAR* argv[])
{
const int nMax = 1000;
int Data[nMax];
srand((unsigned)time(NULL)); // 设置种子
for (int n = 0; n < nMax; ++n)
{
Data[n] = rand();
}
//BubbleSort<int>(Data, nMax);
InsertSort(Data, nMax);
for (int n = 0; n < nMax; ++n)
{
cout << Data[n] << " ";
}
system("pause");
return 0;
}
本文向大家介绍一个C++实战项目：C++实现雪花算法(SnowFlake)产生唯一ID，主要涉及雪花算法、算法知识等，具有一定的C++实战价值，感兴趣的朋友可以参考一下。
本文介绍一个C++代码片段：如何在C++中删除一个文件目录下的所有文件及目录，感兴趣的朋友可以参考一下。
本文介绍C++实现线程同步的四种方式：事件对象、互斥对象、临界区、信号量，感兴趣的朋友可以参考一下。
本文介绍C++内存泄漏的检测与定位方法，感兴趣的朋友可以参考一下。
本文向大家介绍一个C++实战项目：C++实现一个多线程安全的队列容器模板类，主要涉及C++模板类的使用、互斥体实现多线程安全、队列数据结构等知识，具有一定的C++实战价值，感兴趣的朋友可以参考一下。
本文实现C++中UTF-8与GB2312相互转换，感兴趣的朋友可以参考一下。
