#include#include#include#include#includeusing namespace std;
void print(int a[], int n, int i) {
cout << i << ":"; for (int j = 0; j<8; j++) { cout << a[j] << " "; } cout << endl; } void swap(int a, int b) { int temp; temp = a; a = b; b = temp; } /*插入排序: 将第1待排序序列第1个元素看作1个有序序列，把第2个元素到最后1个元素当做是未排序序列。 从头到尾顺次扫描未排序序列，将扫描到的每一个元素插入有序序列的适当位置。 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。 * 时间复杂度也为O(n^2), 比冒泡法和选择排序的性能要更好1些 */ void InsertSort(int a[], int n) { for (int i = 1; i
1; j--)
{
if(a[j] i; j--)
{
if (a[j] < a[j - 1]) swap(a[j], a[j - 1]); } } } /*快速排序 从数列中挑出1个元素，称为 “基准”（pivot）， 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任1边）。在这个分区退出以后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。*/ void QuickSort(int a[], int n)//n为数组的长度 { int low=0,high=n⑴; int temp,temq; int pivot=a[low];//枢轴值 if(n >1 )
{
while(low = pivot )
--high;
a[low]= a[high];//比pivot小的都放在左侧
while(low=1; div/=2)
{
for(int i=div; i=0; j-=div)
swap(a[j],a[j-div]);
}
}
}
/*堆排序
首先，按堆的定义将数组R[0..n]调剂为堆（这个进程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n⑴]调剂为堆，交换R[0]和R[n⑴]；
如此反复，直到交换了R[0]和R[1]为止。
只不过直接选择排序中，为了从R[1...n]当选择最大记录，需比较n⑴次，然后从R[1...n⑵]当选择最大记录需比较n⑵次。
事实上这n⑵次比较中有很多已在前面的n⑴次比较中已做过，而树形选择排序恰好利用树形的特点保存了部份前面的比较结果，
因此可以减少比较次数。对n个关键字序列，最坏情况下每一个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。
堆排序为不稳定排序，不合适记录较少的排序。
*/
void HeapAdjust(int a[],int i,int n) //调剂堆
{
int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号
int max=i; //临时变量
if(i<=n/2) //如果i不是叶节点就不用进行调剂 { if(lchild<=n&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=n&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,n); //避免调剂以后以max为父节点的子树不是堆
}
}
}
void BuildHeap(int a[],int n) //建立堆
{
int i;
for(i=n/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,n);
}
}
void HeapSort(int a[],int n) //堆排序
{
int i;
BuildHeap(a,n);
for(i=n;i>=1;i--)
{
//cout<= n⑴)
right = n-b;
else right = length;
int* temp = new int[length+right];
int i=0, j=0;
while(i<=length⑴ && j<=right⑴){ if(data[a+i] <= data[b+j]){ temp[i+j] = data[a+i];i++; } else{ temp[i+j] = data[b+j]; j++; } } if(j == right){//a中还有元素，且全都比b中的大,a[i]还未使用 memcpy(temp + i + j, data + a + i, (length - i) * sizeof(int)); } else if(i == length){ memcpy(temp + i + j, data + b + j, (right - j)*sizeof(int)); } memcpy(data+a, temp, (right + length) * sizeof(int)); delete [] temp; } void MergeSort(int* data, int n){ int step = 1; while(step < n){ for(int i=0; i<=n-step⑴; i+=2*step) Merge(data, i, i+step, step, n); //将i和i+step这两个有序序列进行合并 //序列长度为step //当i以后的长度小于或等于step时，退出 step*=2;//在按某1步长归并序列以后，步长加倍 } } /* 基数排序 可以对个位数、10位数、百位数也依照这类方法进行排序，最后就可以得到排序完成的序列。 */ int maxbit(int data[], int n) //辅助函数，求数据的最大位数 { int d = 1; //保存最大的位数 int p = 10; for(int i = 0; i < n; ++i) { while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每一个桶中的记录数 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置顺次分配给每一个桶 for(j = n - 1; j >= 0; j--) //将所有桶中记录顺次搜集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; } delete[]tmp; delete[]count; } //主程序 int main() { int n; cin>>n;
int k=n;
int* a=new int[n];
while(k--){
cin>>a[n-k⑴];
}
//int a[8] = { 3,1,5,7,2,4,9,6 };
InsertSort(a, 8);
//BubbleSort(a, 8);
//DirectSort(a, 8);
//radixsort(a,8);
//HeapSort(a,8);
//ShellSort(a,8);
//QuickSort(a,8);
//MergeSort(a,8);
print(a, 8, 8);
}