本文所有排序算法均为升序排序
typedef int dataType;
//这里主要针对整型数据进行排序
typedef struct
{
vector key; //顺序表关键字
int length; //顺序表长度
}List;
这里 vector<datatype></datatype>表示以储存 dataType类型的 vector定义的对象 key
在本文中的用途与数组基本无差别，可用 dataType key[SIZE];代替
使用 vector不要忘了
#inlude
一、插入排序
//排序部分为0-L.length-1
void InsertSort_0(List &L)//对顺序表L进行插入排序
{
int i,j;
dataType temp;
for(i=1;i=0;j--)//向前寻找应该插入该数据的位置
{
if(L.key[j]>temp)
L.key[j+1] = L.key[j];
else
break;
}
L.key[j+1] = temp;
}
}
将顺序表的0号位置清空，作为哨兵位，在1到length的位置放置数据，可以省去循环出口判断的时间,也无需额外的变量来临时储存插入的数据
//排序部分为1-L.length
void InsertSort_1(List &L)
{
int i,j;
for(i=2;iL.key[0])
L.key[j+1]=L.key[j];
else
break;
}
L.key[j+1] = L.key[0];
}
}
在寻找插入数据应该插入的位置时本质上是在做一个顺序查找，我们可以用二分查找取而代之，能够更大程度地减小复杂度
//排序部分为1-L.length
void InsertSort_2(List &L)
{
int i,j,k;
int low,high,mid;
for(i=2;iL.key[0])
high = mid-1; //在前一段区间查找
else
low = mid+1; //在后一段区间查找
}
//low即为应插入位置
//将有序部分插入位置后面的所有点后移一位
for(j=i-1;j>=low;j--)
L.key[j+1] = L.key[j];
L.key[low] = L.key[0];
}
}
二、希尔排序
//排序部分为1-L.length
void ShellInsert(List &L,int d)//增量为d的插入排序(以插入排序的改进版本1为基础)
{
int i,j;
for(i=d+1;i=0;j-=d)
{
if(L.key[j]>L.key[0])
L.key[j+d] = L.key[j];
else
break;
}
L.key[j+d] = L.key[0];
}
}
void ShellSort(List &L)
{
int i;
for(i=L.length/2;i>=1;i/=2)
ShellInsert(L,i);
}
三、冒泡排序
//排序部分为0-L.length-1
void BubbleSort(List &L)
{
int i,j;
dataType temp;
for(i=1;iL.key[j+1])
{
temp = L.key[j];
L.key[j] = L.key[j+1];
L.key[j+1] = temp;
}
}
}
当序列相对有序时无需进行过多的比较操作，每次冒泡记录下最后一次交换的位置，从0位置到标记位置即是无序部分，下一次冒泡只需比较到这里即可，当标记位置为0时，冒泡结束
//排序部分为0-L.length-1
void BubbleSort_1(List &L)
{
int i,sig,lastchange;
dataType temp;
sig = L.length-1;
while(sig>0)
{
lastchange = 0;
for(i=0;iL.key[i+1])
{
temp = L.key[i];
L.key[i] = L.key[i+1];
L.key[i+1] = temp;
lastchange = i;
}
}
sig = lastchange;
}
}
四、快速排序
//排序部分为0-L.length-1
int pivot(List &L,int low,int high)//一趟快速排序，返回枢轴的位置
{
dataType temp = L.key[low];
while(low=temp)//从右边找到比枢轴小的数据
high--;
L.key[low] = L.key[high];
while(low
五、选择排序
//排序部分为0-L.length-1
void SelectSort(List &L)
{
int i,j,k;
dataType temp;
for(i=0;iL.key[j])
{
temp = L.key[j];
k = j;
}
}
L.key[k] = L.key[i];
L.key[i] = temp;
}
}
六、堆排序
建堆的过程中需要从L.length/2开始到0依次进行调整即可
//堆的结构采用顺序表形式储存
//为了做到升序排序，我们要构建一个大顶堆
//排序部分为1-L.length
void HeapAdjust(List &L,int low,int high)
{
int i=low,j=2*i;
L.key[0] = L.key[low];
while(jL.key[j]) //选取大的子树
j++;
if(L.key[j] > L.key[0]) //如果子树数据比其本身大，进行调整
{
L.key[i] = L.key[j];
i = j;
j = 2*i;
}
else
break;
}
L.key[i] = L.key[0];
}
void HeapSort(List &L)
{
int i;
for(i=L.length/2;i>0;i--) //建成大顶堆
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--) //逐个移动，移动后调整
{
L.key[0] = L.key[1];
L.key[1] = L.key[i];
L.key[i] = L.key[0];
HeapAdjust(L,1,i-1);
}
}
七、归并排序
先不断地对数组进行递归平分，一直分到不能再分，然后回溯的过程中两两进行数组归并操作
//排序部分为1-L.length
void Merge(List &S,List &L,int low,int mid,int high)
{
//将有序的S(low到mid)和有序的S(mid+1到high)归并成有序的T(low到high)
//这个函数的操作相当于两个数组的异地归并
int i = low,j = mid+1,k = low;
while(i
//排序部分为1-L.length
void Merge(List &S,List &L,int low,int mid,int high); //归并部分仍用之前的代码
void MergeSort_1(List &L)
{
int len,i,j;
List S = L;
for(len=1;len
八、基数排序
在此算法中用到了vector的几个函数成员，在此进行说明
push_back(); //相当于出栈
size(); //返回vector的长度，相当于数组长度
clear(); //将vector中所有数据清空
typedef struct //队列结构
{
vector data;
int start = 0;
}Queue;
//排序部分为0-L.length-1
void RadixSort(List &L)
{
//对0-9999的数据进行基数排序
const int maxIndex = 4;
int i,k;
int radix = 1;
int n;
Queue Q[10];
for(k=1;k
//排序部分为0-L.length-1
void RadixSort_1(List &L)
{
int i,k;
int maxIndex;
int radix = 1;
int n;
Queue Q[2];
dataType max = L.key[0];
for(i=0;imax)
max = L.key[i];
maxIndex = sqrt(max)+1;
for(k=1;k
本文持续更新中，如有错误或不足之处，欢迎批评指正。
Original: https://www.cnblogs.com/Vergissmeinnicht-rj/p/16336179.html
Author: Vergissmeinnicht_z
Title: 八大排序算法C/C++代码实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604741/
转载文章受原作者版权保护。转载请注明原作者出处！