#include <iostream>#include <ctime>const int SIZE = 100;const int MAX = 1000;using namespace std;//交换数据void Swap(int &a, int &b){ int temp = a; a = b; b = temp;}//冒泡排序void BubbleSort(int *arr, int size){ int i, j; for(i=0;i<size-1;i++) for(j=size-1;j>i;j--) if(arr[j] < arr[j-1]) Swap(arr[j], arr[j-1]);}//选择排序void SelectionSort(int *arr, int size){ int i, j, min; //找出从a[i]到a[size-1]的最小元素的位置 for(i=0;i<size-1;i++) { min = i; for(j=i+1;j<size;j++) if(arr[min] > arr[j]) min = j; //将a[i]与a[min]的数据交换 Swap(arr[i], arr[min]); }}//插入排序void InsertSort(int *arr, int size){ int fOut, loc, temp; for(fOut=1;fOut<size;fOut++) if(arr[fOut] < arr[fOut-1]) { temp = arr[fOut]; loc = fOut; do { arr[loc] = arr[loc-1]; loc--; }while(loc>0 && arr[loc-1]>temp); arr[loc] = temp; }}//快速排序int Partition(int *arr, int first, int last){ int i, small, x; //为了减少最差情况的出现频率而作的一种优化 swap(arr[first], arr[ (first+last)/2 ]); x = arr[first]; small = first; for(i=first+1;i<=last;i++) if(arr[i] < x) { small++; swap(arr[small], arr[i]); } swap(arr[first], arr[small]); return small;}void RecQuick(int *arr, int first, int last){ int pivotLoc; if(first < last) { pivotLoc = Partition(arr, first, last); RecQuick(arr, first, pivotLoc-1); RecQuick(arr, pivotLoc+1, last); }}void QuickSort(int *arr, int size){ RecQuick(arr, 0, size-1);}//计数排序void CountSort(int *arr, int size){ int temp[MAX] = {0}; int i, j; for(i=0;i<size;i++) temp[arr[i]]++; j = 0; for(i=0;i<MAX;i++) { while(0 != temp[i]) { arr[j] = i; temp[i]--; j++; } }}//归并排序void Merge(int *arr, int start, int mid, int end){ int temp1[SIZE], temp2[SIZE]; int n1, n2; int i, j, k; n1 = mid - start + 1; n2 = end - mid; //拷贝前半部分数组 for(i=0;i<n1;i++) temp1[i] = arr[start + i]; //拷贝后半部分数组 for(i=0;i<n2;i++) temp2[i] = arr[mid + i + 1]; //把后面的元素设置的很大 temp1[n1] = temp2[n2] = INT_MAX; i = j = 0; // 逐个扫描两部分数组然后放到相应的位置去 for(k=start;k<=end;k++) { if(temp1[i] <= temp2[j]) { arr[k] = temp1[i]; i++; } else { arr[k] = temp2[j]; j++; } }}void RecMerge(int *arr, int start, int end){ int i; if(start < end) { i = (start + end) / 2; RecMerge(arr, start, i); RecMerge(arr, i+1, end); Merge(arr, start, i, end); }}void MergeSort(int *arr, int size){ RecMerge(arr, 0, size-1);}//堆排序void Heapify(int *arr, int low, int high){ int large; int temp = arr[low]; large = 2 * low + 1; while(large <= high) { if(large<high && arr[large]<arr[large+1]) large = large + 1; if(temp > arr[large]) break; else { arr[low] = arr[large]; low = large; large = 2 * low + 1; } } arr[low] = temp;}void BuildHeap(int *arr, int size){ int i; for(i=size/2-1;i>=0;i--) Heapify(arr, i, size-1);}void HeapSort(int *arr, int size){ int i; //lastOfOrder BuildHeap(arr, size); for(i=size-1;i>=0;i--) { swap(arr[0], arr[i]); Heapify(arr, 0, i-1); }}//希尔排序void ShellSort(int *arr, int size){ int i, j, k, temp; //i为增量 for(i=size/2;i>0;i/=2) { for(j=i;j<size;j+=i) { temp = arr[j]; k = j; while(k-i>=0 && temp<arr[k-i]) { arr[k] = arr[k-i]; k -= i; } arr[k] = temp; } }}//输出数组里的数据void Print(int *arr, int size){ int i; for(i=0;i<size;i++) { printf("%6d ", arr[i]); if(0 == (i+1) % 10) cout << endl; } cout << endl;}//主函数//先随机选择100个整型数据放入数组中，并输出//然后将其从小到大排序，并输出int main(){ int arr[SIZE], i; cout << "The array is: " << endl; srand((unsigned)time(0)); for(i=0;i<SIZE;i++) arr[i] = rand() % MAX; Print(arr, SIZE); //请选择其中一个排序算法，以运行该程序 //BubbleSort(arr, SIZE); //SelectionSort(arr, SIZE); //CountSort(arr, SIZE); //InsertSort(arr, SIZE); //SelectionSort(arr, SIZE); //QuickSort(arr, SIZE); //MergeSort(arr, SIZE); //HeapSort(arr, SIZE); ShellSort(arr, SIZE); cout << "After sorting, the array is:" << endl; Print(arr, SIZE); return 0;}
联系客服
