c++常见排序算法.docx

1、c+常见排序算法/* 气泡排序，快速排序，插入排序，希尔排序，选择排序，堆排序 ，归并排序，基数排序*/#include #include#define Max 100000000using namespace std;templateclass SortRpublic: SortR() arr = new TMax; SortR() deletearr; void InputValue(); void BubbleSort(); /冒泡排序 void QuickSort(); /快速排序 void InsertSort(); /插入排序 void HillSort(); /希尔排序 void

2、 SelectSort(); /选择排序 void HeapSort(); /堆排序 void MergeSort(); /归并排序 void BaseSort(); /基数排序 void Display(T*); /输出排序结果private: void Swap(T*, T*)const; int findPivot(int, int, T*)const; int Partition(int, int, T, T*)const; void QuickSortRev(int, int, T*); /快排递归 void PushDown(int, int,T*)const; /堆排序，整理堆

3、void Merge_array(T*,int,int,int,T*); /合并两个数组 void merge_sort(T*, int, int, T*); /归并排序，递归实现 T GetDigit(T x, int d); void msdradix_sort(T*,int,int,int); T *arr; int n;templatevoid SortR:InputValue() cout n; n = 10000; cout 输入数组元素：; srand(T)time(NULL); for (int i = 0; i arri; arri = rand() %100000;temp

4、latevoid SortR:Swap(T*t1, T*t2)const /交换 T temp; temp = *t1; *t1 = *t2; *t2 = temp;/* -冒泡排序- */templatevoid SortR:BubbleSort() /-时间测试 clock_t start, finish; double totaltime; start = clock();/- T *bubble_arr = new Tn; for (int i = 0; i n; i+) bubble_arri = arri; for (int i = 0; ii; j-) if (bubble_ar

5、rjbubble_arrj - 1) /后面的比前一个小就交换 Swap(&bubble_arrj, &bubble_arrj - 1); finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒 endl; /Display(bubble_arr); /Display(arr);/* -快速排序- */templateint SortR:findPivot(int i, int j, T*quick_arr)const T firstkey; int k; f

6、irstkey = quick_arri; for (k = i + 1; k firstkey) return k; else if (quick_arrkfirstkey) return i; else return -1; /没有不同关键字 return 0;templateint SortR:Partition(int i, int j, T piovt, T *quick_arr)const int l = i, r = j; do Swap(&quick_arrl, &quick_arrr); while (quick_arrl= piovt) r-; while (l = r);

7、 return l;templatevoid SortR:QuickSortRev(int i, int j, T *quick_arr) T piovt; int piovtindex; int k; piovtindex = findPivot(i, j, quick_arr); if (piovtindex = 0) piovt = quick_arrpiovtindex; k = Partition(i, j, piovt, quick_arr); /Display(quick_arr); /输出 return; QuickSortRev(i, k - 1, quick_arr); Q

8、uickSortRev(k, j, quick_arr); templatevoid SortR:QuickSort() /-时间测试 clock_t start, finish; double totaltime; start = clock(); T *quick_arr = new Tn; for (int i = 0; i n; i+) quick_arri = arri; QuickSortRev(0, n - 1, quick_arr); /- finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_S

9、EC; cout 运行时间： totaltime 秒 endl; /Display(arr);/*-插入排序-*/templatevoid SortR:InsertSort() /插入排序 /-时间测试 clock_t start, finish; double totaltime; start = clock(); T *insert_arr = new Tn; for (int i = 0; i n; i+) insert_arri+1 = arri; insert_arr0 = -1; for (int i = 1; in; i+) int j = i; while (insert_ar

10、rjinsert_arrj - 1) Swap(&insert_arrj, &insert_arrj - 1); j-; /- finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒 endl; /for (int i = 1; i = 20; i+) / cout insert_arri ; /cout endl; /Display(arr);/*-希尔排序-*/templatevoid SortR:HillSort() /-时间测试 clock_t sta

11、rt, finish; double totaltime; start = clock(); T *hill_arr = new Tn; for (int i = 0; i 0;gap/=2) for (j = gap; j n; j+) if (hill_arrj = 0 & hill_arrktemp) hill_arrk + gap = hill_arrk; k -= gap; hill_arrk + gap = temp; /Display(hill_arr); /- finish = clock(); totaltime = (double)(finish - start) / CL

12、OCKS_PER_SEC; cout 运行时间： totaltime 秒 endl;/*-选择排序-*/templatevoid SortR:SelectSort() /-时间测试 clock_t start, finish; double totaltime; start = clock(); T *select_arr = new Tn; for (int i = 0; i n; i+) select_arri = arri; T minindex; /存储最小的元素 for (int i = 0; in; i+) minindex = select_arri; for (int j =

13、i + 1; jn; j+) if (select_arrjminindex) minindex = select_arrj; Swap(&select_arri, &minindex); /Display(select_arr); /- finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒 endl;/*-堆排序-*/ templatevoid SortR:PushDown(int first, int last,T *heap_arr)const int

14、 r; r = first; while (r heap_arr2 * r) Swap(&heap_arr2*r,&heap_arrr); r = last; else if (heap_arrr heap_arr2 * r) & (heap_arr2*r heap_arr2 * r + 1) & (heap_arr2 * r+1 = heap_arr2*r) /r与右儿子交换 Swap(&heap_arr2*r+1, &heap_arrr); r = r * 2 + 1; else r = last; templatevoid SortR:HeapSort() /-时间测试 clock_t

15、start, finish; double totaltime; start = clock(); T *heap_arr = new Tn; for (int i = 0; i = 1; i-) PushDown(i, n, heap_arr); for (i = n; i1; i-) Swap(&heap_arr1, &heap_arri); PushDown(1,i-1, heap_arr); /- finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒

16、 0; i-) cout heap_arri ; cout endl;*/*-归并排序-*/templatevoid SortR:Merge_array(T*merge_arr, int first, int midle, int last, T*temp) int i = first, j = midle + 1; int m = midle, l = last, k = 0; while (i = m & j = l) if (merge_arri = merge_arrj) tempk+ = merge_arri+; else tempk+ = merge_arrj+; while (i

17、 = m) tempk+ = merge_arri+; while (j = l) tempk+ = merge_arrj+; for (i = 0; i k; i+) merge_arrfirst + i = tempi;templatevoid SortR:merge_sort(T*merge_arr,int first,int last,T*temp) if (first last) int mid = (first + last) / 2; merge_sort(merge_arr, first, mid, temp); merge_sort(merge_arr, mid + 1, l

18、ast, temp); Merge_array(merge_arr, first, mid, last, temp); templatevoid SortR:MergeSort() /-时间测试 clock_t start, finish; double totaltime; start = clock(); T *merge_arr = new Tn; for (int i = 0; i n; i+) merge_arri + 1 = arri; T *p = new Tn; merge_sort(merge_arr, 1, n, p); /- finish = clock(); total

19、time = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒 endl; /*for (int i = 1; i = n; i+) cout merge_arri ; cout endl;*/*-基数排序-*/templateT SortR:GetDigit(T x, int d) int a = 1, 1, 10;/排的是100以内的 return (x / ad) % 10;templatevoid SortR:msdradix_sort(T *base_arr,int first,int last,int

20、 d) int radix = 10; int count10, i, j; for (i = 0; i radix; i+) counti = 0; T*bucker = new Tn; for (i = first; i = last; i+) countGetDigit(base_arri, d)+; for (i = 1; i = first; -i) j = GetDigit(base_arri, d); buckercountj - 1 = base_arri; -countj; for (i = first,j = 0; i = last; i+,j+) base_arri =

21、buckerj; for (i = 0; i radix; i+) int p1 = first + counti; int p2 = first + counti + 1 - 1; if (p11) msdradix_sort(base_arr, p1, p2, d - 1); templatevoid SortR:BaseSort() /*cout 输入所要排的数（先默认0-99的,n值还是最开始的）：endl; T *base_arr = new Tn; for (int i = 0; i base_arri;*/ /-时间测试 clock_t start, finish; double

22、 totaltime; start = clock(); T *base_arr = new Tn; for (int i = 0; i n; i+) base_arri = arri; msdradix_sort(base_arr, 0, n - 1, 2); /- finish = clock(); totaltime = (double)(finish - start) / CLOCKS_PER_SEC; cout 运行时间： totaltime 秒 endl; cout 排序结果： endl; /Display(base_arr);/*-输出函数-*/templatevoid Sort

23、R:Display(T *newarray) for (int i = 0; i20; i+) cout newarrayi ; cout endl;/*-主函数-*/int main() cout 排序方法（从小到大）： endl; SortR mysort; mysort.InputValue(); cout 气泡排序： endl; mysort.BubbleSort(); cout 快速排序： endl; mysort.QuickSort(); cout 插入排序： endl; mysort.InsertSort(); cout 希尔排序： endl; mysort.HillSort(); cout 选择排序： endl; mysort.SelectSort(); cout 堆排序： endl; mysort.HeapSort(); cout 归并排序： endl; mysort.MergeSort(); cout 基数排序： endl; mysort.BaseSort(); system(pause); return 0;/*