|
一、冒泡排序
冒泡排序是一种简单的排序方法，算法如下：
1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推…)，直至再也不能交换。
代码实现如下：
#include <iostream>
using namespace std;
/*交换函数，作用是交换数组中的两个元素的位置*/
void swap(int array[],int i,int j)
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
/*冒泡排序*/
void BubbleSort(int array[],int n)
{
for(int i=0;i<n-1;i++)
{
for(int j=n-1;j>i;j--)
{
if(array[j]<array[j-1])
swap(array,j,j-1);
}
}
}
int main()
{
int array[5]={3,1,2,5,4};
BubbleSort(array,5);
for(int i=0;i<5;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
最差时间复杂度 O(n2)
最优时间复杂度 O(n)
平均时间复杂度 O(n2)
最差空间复杂度 O(n) total, O(1) auxiliary
二、插入排序
插入排序也是一种简单排序方法，算法如下：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
代码实现如下：
#include <iostream>
using namespace std;
/*交换函数，作用是交换数组中的两个元素的位置*/
void swap(int array[],int i,int j)
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
/*插入排序*/
void InsertSort(int array[],int n)
{
for(int i=1;i<n;i++)
{
for(int j=i;j>0;j--)
{
if(array[j]>array[j-1])
swap(array,j,j-1);
else
break;
}
}
}
int main()
{
int array[5]={3,1,2,5,4};
InsertSort(array,5);
for(int i=0;i<5;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
最差时间复杂度 O(n2)
最优时间复杂度 O(n)
平均时间复杂度 O(n2)
最差空间复杂度 O(n) total, O(1) auxiliary
三、选择排序
选择排序的思想如下：
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n－1算法结束，否则回到第3步
代码实现如下：
#include <iostream>
using namespace std;
/*交换函数，作用是交换数组中的两个元素的位置*/
void swap(int array[],int i,int j)
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
/*选择排序*/
void SelectionSort(int array[],int n)
{
for(int i=0;i<n-1;i++)
{
int smallest=i;
for(int j=i+1;j<n;j++)
{
if(array[smallest]>array[j])
smallest=j;
}
swap(array,i,smallest);
}
}
int main()
{
int array[5]={3,1,2,5,4};
SelectionSort(array,5);
for(int i=0;i<5;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
最差时间复杂度 О(n2)
最优时间复杂度 О(n2)
平均时间复杂度 О(n2)
最差空间复杂度 О(n) total, O(1) auxiliary
以上三种排序的时间复杂度都是O(n2)。
四、快速排序
实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
快速排序的基本算法是：
1. 从数列中挑出一个元素，称为 “基准”（pivot），也叫作支点，
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
代码实现如下：
#include <iostream>
using namespace std;
/*交换函数，作用是交换数组中的两个元素的位置*/
void swap(int array[],int i,int j)
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
/*将轴值放到数组的适当的位置*/
int partition(int array[],int left,int right)
{
int mid=(left+right)/2;
int tmp=array[mid];
swap(array,mid,right);
int i=left;
int j=right;
while(1)
{
/*i指针向右移动，直到找到一个大于轴值的值*/
while(1)
{
/*如果i与j相遇则确定轴值位置，将其返回*/
if(i==j)
{
array[i]=tmp;
return i;
}
if(array[i]>tmp)
{
array[j]=array[i];
j--;
break;
}
i++;
}
/*j指针向左移动，直到找到一个小于轴值的值*/
while(1)
{
/*如果i与j相遇则确定轴值位置，将其返回*/
if(i==j)
{
array[j]=tmp;
return j;
}
if(array[j]<tmp)
{
array[i]=array[j];
i++;
break;
}
j--;
}
}
}
/*快速排序*/
void quickSort(int array[],int left,int right)
{
if(right<=left)
return;
int pivot=partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
int main()
{
int array[8]={6,8,7,3,1,2,5,4};
quickSort(array,0,7);
for(int i=0;i<8;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
快速排序的时间复杂度是O(nlogn)，但是最坏情况下复杂度是O(n2)。
最差时间复杂度 Θ(n2)
最优时间复杂度 Θ(nlogn)
平均时间复杂度 Θ(nlogn) comparisons
最差空间复杂度 根据实现的方式不同而不同。
五.希尔排序（shell sorting）
增量为2的shell排序的时间代价可以达到θ(n的3/2次方)，有的增量可以达到θ(n的7/6次方)，很接近θ(n)。
代码实现：
.#include <iostream>
using namespace std;
/*交换函数，作用是交换数组中的两个元素的位置*/
void swap(int array[],int i,int j)
{
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
/*希尔排序*/
void ShellSort(int array[],int n)
{
for(int delta=n/2;delta>0;delta/=2)
{
for(int i=0;i<delta;i++)
{
for(int j=i+delta;j<n;j+=delta)
{
for(int k=j;k>0;k-=delta)
{
if(array[k]<array[k-1])
swap(array,k,k-1);
}
}
}
}
}
int main()
{
int array[8]={6,8,7,3,1,2,5,4};
ShellSort(array,8);
for(int i=0;i<8;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
六.归并排序（merge sorting）
归并排序的最大时间代价，最小时间代价和平均时间代价均为θ(n*logn)。归并排序不依赖于原始数组的有序程度。
代码实现：
#include <iostream>
using namespace std;
/*归并过程--将两个有序数组合并成一个有序数组*/
void merge(int array[],int tempArray[],int left,int right,int middle)
{
int i;
int index1=left;
int index2=middle+1;
for(i=left;(index1<=middle)&&(index2<=right);i++)
{
if(array[index1]<array[index2])
tempArray[i]=array[index1++];
else
tempArray[i]=array[index2++];
}
while(index1<=middle)
tempArray[i++]=array[index1++];
while(index2<=right)
tempArray[i++]=array[index2++];
for(i=left;i<=right;i++)
array[i]=tempArray[i];
}
/*两路归并排序--array[]为待排数组，tempArray[]为临时数组，left和right分别是数组两端*/
void mergeSort(int array[],int tempArray[],int left,int right)
{
if(left<right)
{
int middle=(left+right)/2;
mergeSort(array,tempArray,left,middle);
mergeSort(array,tempArray,middle+1,right);
merge(array,tempArray,left,right,middle);
}
}
int main()
{
int array[8]={6,8,7,3,1,2,5,4};
int tempArray[8];
mergeSort(array,tempArray,0,7);
for(int i=0;i<8;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
七.堆排序（heap sorting）
堆排序的最大时间代价，最小时间代价和平均时间代价均为θ(n*logn)。堆排序和归并排序一样，不依赖于原始数组的有序程度。
代码实现：
#include <iostream>
#include "MaxHeap.h"
using namespace std;
/*最大堆排序函数*/
void heapSort(int array[],int n)
{
MaxHeap max_heap=MaxHeap(array,n);
/*删除堆的最大值（堆顶），即每次将最大值与数组的最后一个元素交换位置*/
for(int i=0;i<7;i++)
max_heap.removeMax();
}
int main()
{
int array[8]={4,3,7,1,2,8,5,6};
heapSort(array,8);
for(int i=0;i<8;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
#include <iostream>
using namespace std;
/*最大堆定义*/
class MaxHeap
{
private:
int size; //最大堆的元素数目
int * array; //最大堆数组的首地址指针
public:
MaxHeap(int array[],int n); //用已有数组初始化一个最大堆
void buildHeap(); //构建最大堆
void siftDown(int index); //向下筛选法
void swap(int index1,int index2); //交换位置为index1与index2的元素
void removeMax(); //删除堆顶的最大值--与数组最后一个元素交换位置并重新构建最大堆
int leftChild(int index); //返回左孩子的位置
int rightChild(int index); //返回右孩子的位置
};
#include <iostream>
#include "MaxHeap.h"
using namespace std;
/*最大堆成员函数实现*/
MaxHeap::MaxHeap(int array[],int n)
{
this->array=array;
size=n;
buildHeap();
}
void MaxHeap::buildHeap()
{
for(int i=size/2-1;i>=0;i--)
siftDown(i);
}
void MaxHeap::siftDown(int index)
{
int max_index=leftChild(index);
while(max_index<size)
{
if(max_index<size-1&&array[rightChild(index)]>array[max_index])
max_index++;
if(array[index]>array[max_index])
break;
swap(index,max_index);
index=max_index;
max_index=leftChild(index);
}
}
void MaxHeap::swap(int index1,int index2)
{
int temp=array[index1];
array[index1]=array[index2];
array[index2]=temp;
}
void MaxHeap::removeMax()
{
swap(0,size-1);
size--;
siftDown(0);
}
int MaxHeap::leftChild(int index)
{
return index*2+1;
}
int MaxHeap::rightChild(int index)
{
return index*2+2;
}
八.桶排序 (Bucket sort)
1,稳定
2,常见排序里最快的一种,比快排还要快…大多数情况下
3,非常耗空间,基本上是空间复杂度最高的一种排序算法
代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
void bucket_sort(unsigned * arr,int len)
{
unsigned *buckets[10];//指针数组
unsigned n=1;//用于取整数各位上的值
int index;//数组下标计数索引
int indexs[10];//各个桶下标计数索引
int i,j;//分配动态内存作为桶
for(i=0; i<10; ++i)
buckets[i]=(unsigned *)malloc(sizeof(unsigned)*len);
while(1)
{
//计数索引清零
index=0;
for(i=0; i<10; ++i)
indexs[i]=0;//数组至桶
for(i=0; i<len; ++i)
buckets[arr[i]/n%10][indexs[arr[i]/n%10]++]=arr[i];//桶至数组
for(i=0; i<10; ++i)
for(j=0; j<indexs[i]; ++j)
arr[index++]=buckets[i][j];//为取元素的下一位做准备
n*=10;//判断是否该结束
for(i=0; arr[i]<n&&i<len; ++i);
if(i==len) break;
}//释放动态内存
for(i=0; i<10; ++i)
free(buckets[i]);
}
void print(unsigned * arr,int len)
{
int i=0;
for(i=0; i<len; ++i)
{
printf("%8d",arr[i]);//5个元素一行
if((i+1)%5==0)
printf("\n");
}
}
int main()
{
unsigned array[1002];
int i=0;//为数组元素随机赋值
for(i=0; i<1002; ++i)
array[i]=rand();
printf("排序前\n");
print(array,1002);//排序
bucket_sort(array,1002);
printf("排序后\n");
print(array,1002);
return 0;
}
平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高.
最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)
九.基数排序（radix sorting）
基数排序的时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。基数排序法是属于稳定性的排序。
代码实现：
#include <iostream>
using namespace std;
/*计算关键字位数的最大值*/
int KeySize(int array[],int size)
{
int key_size=1;
for(int i=0;i<size;i++)
{
int temp=1;
int n=10;
while(array[i]/n>0)
{
temp++;
n*=10;
}
key_size=(temp>key_size)?temp:key_size;
}
return key_size;
}
/*基数排序*/
void RadixSort(int array[],int size)
{
int bucket[10][10]={0};//定义基数桶
int order[10]={0};//保存每个基数桶之中的元素个数
int key_size=KeySize(array,size);//计算关键字位数的最大值
for(int n=1;key_size>0;n*=10,key_size--)
{
/*将待排序的元素按照关键值的大小依次放入基数桶之中*/
for(int i=0;i<size;i++)
{
int lsd=(array[i]/n)%10;
bucket[lsd][order[lsd]]=array[i];
order[lsd]++;
}
/*将基数桶中的元素重新串接起来*/
int k=0;
for(i=0;i<10;i++)
{
if(order[i]!=0)
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
order[i]=0;
}
}
}
}
int main()
{
int array[10]={73,22,93,43,55,14,28,65,39,81};
int size=sizeof(array)/sizeof(int);
RadixSort(array,size);
for(int i=0;i<size;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}
|
