本文共 5554 字,大约阅读时间需要 18 分钟。
//实现两个个函数,输入数组和数组个数,从小到大排序,要求使用函数模板。//支持 int char float double long。//(一个函数使用快速排序法,一个函数使用插入排序法)templatevoid InsertionSort(T *arr, const int count){ //进行分组,为数组长度的一半 int gap = count / 2; int i = 0; while (gap > 1) { //遍历[i,gap) for (i = 0; i < count - gap; ++i) { //分组后,按组排序 T insert = arr[i + gap]; int pos = i; while (pos >= 0) { if (arr[pos]>arr[pos + gap]) { //交换两个位置 arr[pos + gap] = arr[pos]; arr[pos] = insert; } //更新pos,当pos不小于0就和下一个间隔的数值再比较 pos -= gap; } } gap = gap / 2; } //gap==1,直接插入法 for (i = 1; i < count; ++i) { T insert = arr[i]; int pos = i - 1;//第一个有序,从第二个开始往前插入 while (pos >= 0) { if (arr[pos]>arr[pos + 1]) { arr[pos + 1] = arr[pos]; arr[pos] = insert; } --pos; } } return;}template void swap(T* a, T*b){ T tmp = 0; tmp = *a; *a = *b; *b = tmp; return;}template void QkSort(T *arr, int begin, int end){ //前后指针法 int KeyIndex = end; int start = begin; T key = arr[end];//基准值为最后一个值 //找到中间值的下标,把数组分成左边区(0,mid)和右边区(mid,count-1] //前指针向后走,直到遇到比基准值大的数,停止; //后指针向后走,直到遇到比基准值小的数,停止 //然后交换位置 while (begin >= end) { return; } while (begin < end) { while (begin < end && (arr[begin] <= key)) { ++begin; } while (begin < end && (arr[end] >= key)) { --end; } if (begin < end) { swap(&arr[begin], &arr[end]); } } //当前后指针重合后,交换基准值和开始的指针指向的元素 swap(&arr[begin], &arr[KeyIndex]); int mid = begin;//begin就是中间值的下标 //对左边区进行排序[begin,mid) //对右边区进行排序[mid+1,end] QkSort(arr, start, mid); QkSort(arr, mid + 1, KeyIndex); return;}template void QuickSort(T *arr, const int count){ QkSort(arr, 0, count - 1); return;}//打印template void show(T *arr, const int count){ cout << "The result from low to high:"; for (int i = 0; i < count; ++i) { cout << arr[i] << ' '; } cout << endl;}
#include"sort.h"#include#include #include using namespace std;int main(int argc, char* argv[]){ int input = -1; int count = 0; int num = 0; int* arr1 = NULL; char* arr2 = NULL; float* arr3 = NULL; double* arr4 = NULL; long* arr5 = NULL; int IntMinValue = (numeric_limits ::min)(); char CharMinValue = (numeric_limits ::min)(); float FloatMinValue = (numeric_limits ::min)(); double DoubleMinValue = (numeric_limits ::min)(); long LongMinValue = (numeric_limits ::min)(); int IntMaxValue = (numeric_limits ::max)(); char CharMaxValue = (numeric_limits ::max)(); float FloatMaxValue = (numeric_limits ::max)(); double DoubleMaxValue = (numeric_limits ::max)(); long LongMaxValue = (numeric_limits ::max)(); cout << "double_minvalue£º" << DoubleMinValue << endl; cout << "double_maxvalue£º" << DoubleMaxValue << endl; while (0 != input) { cout << "Select type:input= 1.int 2.char 3.float 4.double 5.long" << endl; cin >> input; if (input < 0 || input>5 || isalpha(input)) { break; } switch (input) { case 1: { cout << "Input a number of Array:" << endl; cin >> count; arr1 = new int[count]; memset(arr1, 0, count); cout << "Array to be sorted: "; for (int i = 0; i < count; ++i) { cin >> arr1[i]; if ((arr1[i] < IntMinValue) && (arr1[i] > IntMaxValue)) { break; } } cout << "Select the method of sort:<0.InsertionSort or 1.QuickSort>"; cin >> num; if (0 == num) { InsertionSort(arr1, count); show(arr1, count); } else if (1 == num) { QuickSort(arr1, count); show(arr1, count); } else { break; } break; } case 2: { cout << "Input a number of Array:" << endl; cin >> count; arr2 = new char[count]; memset(arr2, 0, count); cout << "Array to be sorted: "; for (int i = 0; i < count; ++i) { cin >> arr2[i]; if ((arr2[i] < CharMinValue) && (arr2[i] > CharMaxValue)) { break; } } cout << "Select the method of sort:<0.InsertionSort or 1.QuickSort>"; cin >> num; if (0 == num) { InsertionSort(arr2, count); show(arr2, count); } else if (1 == num) { QuickSort(arr2, count); show(arr2, count); } else { break; } break; } case 3: { cout << "Input a number of Array:" << endl; cin >> count; arr3 = new float[count]; memset(arr3, 0, count); cout << "Array to be sorted: "; for (int i = 0; i < count; ++i) { cin >> arr3[i]; if ((arr3[i] < FloatMinValue) && (arr3[i] > FloatMaxValue)) { break; } } cout << "Select the method of sort:<0.InsertionSort or 1.QuickSort>"; cin >> num; if (0 == num) { InsertionSort(arr3, count); show(arr3, count); } else if (1 == num) { QuickSort(arr3, count); show(arr3, count); } else { break; } break; } case 4: { cout << "Input a number of Array:" << endl; cin >> count; arr4 = new double[count]; memset(arr4, 0, count); cout << "Array to be sorted: "; for (int i = 0; i < count; ++i) { cin >> arr4[i]; if ((arr4[i] < DoubleMinValue) && (arr4[i] > DoubleMaxValue)) { break; } } cout << "Select the method of sort:<0.InsertionSort or 1.QuickSort>"; cin >> num; if (0 == num) { InsertionSort(arr4, count); show(arr4, count); } else if (1 == num) { QuickSort(arr4, count); show(arr4, count); } else { break; } break; } case 5: { cout << "Input a number of Array:" << endl; cin >> count; arr5 = new long[count]; memset(arr5, 0, count); cout << "Array to be sorted: "; for (int i = 0; i < count; ++i) { cin >> arr5[i]; if ((arr5[i] < LongMinValue) && (arr5[i] > LongMaxValue)) { break; } } cout << "Select the method of sort:<0.InsertionSort or 1.QuickSort>"; cin >> num; if (0 == num) { InsertionSort(arr5, count); show(arr5, count); } else if (1 == num) { QuickSort(arr5, count); show(arr5, count); } else { break; } break; } default: break; } } delete[] arr1; delete[] arr2; delete[] arr3; delete[] arr4; delete[] arr5; return 0;}
转载地址:http://clypi.baihongyu.com/