数据结构之排序算法

#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; i1; 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); }