本文共 4234 字，大约阅读时间需要 14 分钟。
#includeusing namespace std;// void InsertSort(int arr[]) {};// 直接插入排序void InsertSort(int arr[], int n) { int i, j, key; for (i = 1; i < n; i++) { key = arr[i]; for (j = i - 1; j >= 0; j--) { if (key < arr[j]) { arr[j+1] = arr[j]; } else { break; } } arr[j+1] = key; }}// 希尔排序：分组后的插入排序void ShellSort(int arr[], int n) { for (int dk = n/2; dk > 0; dk = dk/2) { int i, j, key; for (i = dk; i < n; i++) { key = arr[i]; for (j = i - dk; j >= 0; j--) { if (key < arr[j]) { arr[j+dk] = arr[j]; } else { break; } } arr[j+dk] = key; } }}// 冒泡排序void BubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { bool flag = false; for (int j = n-1; j > i; j--) { if (arr[j-1] > arr[j]) { swap(arr[j-1], arr[j]); flag = true; } } if (flag == false) { return; } }}// 堆排序// 首先排序成大顶堆void heapify(int arr[], int n, int i) { int lagest = i; int lson = 2 * i + 1; int rson = 2 * i + 2; if (lson < n && arr[lagest] < arr[lson]) { lagest = lson; } if (lson < n && arr[lagest] < arr[rson]) { lagest = rson; } while (lagest != i) { swap(arr[lagest], arr[i]); heapify(arr, n, lagest); }}// 排序入口void heap_sort(int arr[], int n) { for (int i = n /2 - 1; i >= 0; i++) { heapify(arr, n, i); } for (int i = n-1; i > 0; i--) { swap(arr[i], arr[0]); heapify(arr, i, 0); }}// 归并排序/*int low = 0, high = sizeof(arr)/sizeof(int);MergeSort(arr, low, high-1);*/void Merge(int arr[], int start1 , int end1, int start2, int end2) { int n1 = end1 - start1 + 1; int n2 = end2 - start2 + 1; int arr_left[n1], arr_right[n2]; for (int i = 0; i < n1; i++) { arr_left[i] = arr[start1 + i]; } for (int i = 0; i < n2; i++) { arr_right[i] = arr[start2 + i]; } int left = 0, right = 0; int p = start1; while (left < n1 && right < n2) { if (arr_left[left] < arr_right[right]) { arr[p] = arr_left[left]; left++; p++; } else { arr[p] = arr_right[right]; right++; p++; } } while (left < n1) { arr[p] = arr_left[left]; left++; p++; } while (right < n2) { arr[p] = arr_right[right]; right++; p++; }}void MergeSort(int arr[], int low, int high) { if(low < high) { // 此处比mid = (low + high)/2更好的防止内存泄漏 int mid = low + (high - low)/2; // 拆成左边和右边分别递归调用MergeSort MergeSort(arr, low, mid); MergeSort(arr, mid+1, high); // 合并 Merge(arr, low, mid, mid+1, high); }}// 直接选择排序void SelectSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int min = i; for(int j = i + 1; j < n; j++) { if (arr[j] < arr[min]) { min = j; } } if (min != i) { swap(arr[i], arr[min]); } }}// 快速排序/*选定pivot中心轴大于pivot放在他的右边小于pivot放在他的左边*/int Partition(int arr[], int low, int high) { int pivot = arr[low]; while(low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low;}void QuickSort(int arr[], int low, int high) { if (low < high) { int pivotpos = Partition(arr, low, high); QuickSort(arr, low, pivotpos-1); QuickSort(arr, pivotpos + 1, high); }}int main() { int arr[6] = { 2, 1, 5, 4, 3, 8 }; int n = sizeof(arr) / sizeof(arr[0]); // InsertSort(arr, n); // ShellSort(arr, n); // heap_sort(arr, n); QuickSort(arr, 0, n-1); for(int i = 0; i < n; i++) { cout << arr[i] << endl; } return 0;}
转载地址：http://aukpz.baihongyu.com/