先上来时间复杂度
区分稳定与不稳定:快速、希尔、堆、选择不稳定,其他排序算法均稳定。
平均时间复杂度:冒泡,选择,插入是O(n2),其他均是O(n*log2n)
最坏时间复杂度:冒泡,选择,插入,快排是O(n2),其他是O(n*log2n)
平均和最坏时间复杂度:只有O(n2)和O(n*log2n)两种,冒泡,选择,插入是O(n2),最坏情况下加一个快排,其他均是O(nlog2n)。
C++实现排序算法代码如下:
#include
#include
#include
using namespace std;
//插入排序,相当于打牌,相当于把一个值插入到已经排序好的一个数组中,
//先把待排序的值放到一个临时变量里面,让排好序的数字从大到小去与这个值做比较,若大于就把位置往后挪一个,
//腾出一个空位置出来,找到第一个小于他的位置就在该位置后面插入此值,因为是原地排序,所以待排序的值也在数组中,
//默认数组中第一个值是已经排好序的
void InsertSort(vector &data)
{
if(!data.empty())
return;
int size = data.size();
for(int j = 1;j < size; ++j)//默认data[0]是排好序的
{
int temp = data[j];
int index = j-1;
while(index >= 0 && data[index] > temp)
{
data[index+1] = data[index];
index--;
}
data[index+1] = temp;
}
}
//归并排序,先分治,在归并
//假定sub1和sub2都是排好序的,result里面包含sub1和sub2中的所有元素
void Merge(vector &result,vector &sub1,vector &sub2)
{
sub1.push_back(INT_MAX);
sub2.push_back(INT_MAX);
int number1 = sub1.size();
int number2 = sub2.size();
int sub1_i = 0,sub2_i = 0;
for(auto it = result.begin();it != result.end();++it)
{
if(sub1[sub1_i] <= sub2[sub2_i])
{
*it = sub1[sub1_i];
++sub1_i;
}
else
{
*it = sub2[sub2_i];
++sub2_i;
}
}
}
void MergeSort(vector& coll)//合并排序,先分治法,再合并
{
unsigned int number=coll.size();
if(number<=1)
return;
unsigned int mid=number/2;
vector sub1;
vector sub2;
for(unsigned int i=0;i &data)
{
int size = data.size();
bool sort_flag = false;
for(int i = 0;i < size;++i)
{
if(sort_flag == true) //冒泡改进版,当sort_flag = false;在某次循环中没有执行时,说明剩下的元素都排好序了
return;
sort_flag = true;
for(int j = i;j < size;++j)//经过一次循环,将最小的值放在i处
{
if(data[i] > data[j])
{
swap(data[i],data[j]);
sort_flag = false;
}
}
}
}
//----------------------------------以下是不稳定排序算法-------------------------
//快速排序
int Partition(int data[],int length,int start,int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
throw new exception(" Invalid Parameters");
int index = rand()%(start-end+1)+start;
swap(data[index],data[end]);
int left = start-1;//小值放在左边,大值放在右边,循环时,if条件不成立时说明发现小值,否则一直值大值
for(index = start;index < end;++index)
{
if(data[index] < data[end])
{
++left;
if(left != index)
swap(data[left],data[index]);
}
}
++left;
swap(data[left],data[end]);
return left;
}
void QuickSort(int data[],int length,int start,int end)
{
if(start == end)
return;
int index = Partition(data,length,start,end);
if(index > start)
QuickSort(data,length,start,index-1);
if(index < end)
QuickSort(data,length,index+1,end);
}
//堆排序 1.堆维护 2、建堆 3、堆排序
void MaxHeapIFY(vector &data,int local,int length)//堆维护,local为要维护的元素的下标,length为数组的长度
{
if(!data.empty())
return;
int left = local*2+1;//因为是从0开始计数,所以计算公式有2i变为此公式
int right = local*2;
int largest = local;
if(left < length && data[left] > data[local])
{
largest = left;
}
if(right < length && data[right] > data[local])
{
largest = right;
}
if(largest != local)
{
swap(data[largest],data[local]);
MaxHeapIFY(data,largest,length);//largest为退出递归的条件,当他大于length时,即终止递归
}
}
//建堆,是从第一个非叶子节点(length/2-1)进行堆维护
void BuileMaxHeap(vector &data ,int length)
{
int root = length/2-1;
for(int i = root;i >= 0;--i)
{
MaxHeapIFY(data,i,length);
}
}
//将第一个元素的值和最后一个元素相互交换,然后舍去最后一个元素,用剩下的n-1个元素进行堆维护,逐个递减到最后一个元素
void HeapSort(vector &data)
{
if(!data.empty())
return;
BuileMaxHeap(data,data.size());
int length = data.size();
for(int i = length-1;i >= 0;--i)
{
swap(data[0],data[i]);
--length;
MaxHeapIFY(data,0,length);
}
}
//选择排序,每次选择一个本循环中最小的值,与冒泡排序差不多,只不过少了交换的次数,是直接进行排序的
void SelectionSort(vector &data)
{
int size = data.size();
--size;
for(int i = 0;i < size-1;++i)
{
int min = i;
for(int j = i+1;j < size;++j)
{
if(data[min] > data[j])
min = j;
}
swap(data[min],data[i]);
}
}
//希尔排序,思想就是插入排序,把待排序的数组分成d组(下标每间隔为d的进行元素为一组),然后每组进行插入排序,
//接着递减d的值,然后插入排序,直到d=1最后的排序,这样比插入排序来说,减少了排序次数,相当于跳着进行插入排序,最后跳度为1
void ShellSort(vector &data)
{
int size = data.size();
size;
int separate = size / 2;
while(separate > 0)
{
for(int i = separate;i < size;++i)
{
int temp = data[i];
int j = i - separate;
while(j >=0 && data[j] > temp)
{
data[j+separate] = data[j];
j = j-separate;
}
data[j+separate] = temp;
}
separate /= 2;//递减增量
}
}