七种内排序算法，目前只写了代码，原理解析待补充：

1.交换类排序：冒泡、快排；

2.选择类排序：选择、堆排序；

3.插入类排序：直接插入、希尔；

4.归并排序

测试用例：

讯享网

5
1 2 4 3 -3
10
100 293 123 212 293 434 5 12 439 3

Todo：

原理、复杂度解析与稳定性解析。

#include<iostream> using namespace std; int n; //print current array void echo(int a[]) { if (a==nullptr || n <= 0) { cout << "null error" << endl; return; } for (int i = 0; i < n-1; i++) { cout << a[i] << " "; } cout << a[n - 1] << endl; } //swap a[i] and a[j] void swap(int a[], int i, int j) { if (a[i] == a[j]) { return; } a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j]; } //1.Bubble Sort void BubbleSort(int a[]) { if (a == nullptr) { return; } int flag = 1; for (int i = 0; i < n-1 && flag; i++) { flag = 0; for (int j = 0; j < n - i - 1; j++) { if (a[j]>a[j+1]) { flag = 1; swap(a,j,j+1); echo(a); } } } } //2.Quick Sort void QuickSort(int a[], int left, int right) { if (a == nullptr || left >= right) { return; } int i = left, j = right; int tmp = a[i]; while (i<j) { while (i < j && tmp <= a[j]) { --j; } if (i<j) { a[i] = a[j]; } while (i<j && a[i] <= tmp) { ++i; } if (i<j) { a[j] = a[i]; } } a[i] = tmp; echo(a); QuickSort(a, left, i - 1); QuickSort(a, i + 1, right); } //3.Select Sort void SelectSort(int a[]) { for (int i = 0; i < n - 1; i++) { int maxi = 0; for (int j = 0; j < n - i; j++) { if (a[j]>a[maxi]) { maxi = j; } } swap(a, n - i - 1, maxi); echo(a); } } //4.Heap Sort void AdjustHeap(int a[], int i, int last) { int left = 2 * i + 1, right = 2 * i + 2, tmp = a[i]; while (left<last) { int maxi = left; if (right<last && a[left] < a[right]) { maxi = right; } if (tmp < a[maxi]) { a[i] = a[maxi]; i=maxi; left = 2 * i + 1, right = 2 * i + 2; echo(a); } else { break; } } a[i] = tmp; } void InitHeap(int a[]) { int t = (n - 1) / 2; for (; t >= 0; t--) { AdjustHeap(a, t, n); } cout << "heap init done." << endl; } void HeapSort(int a[]) { InitHeap(a); for (int i = 0; i < n - 1; i++) { AdjustHeap(a, 0, n - i); swap(a, 0, n - i - 1); echo(a); } } //5.Insert Sort void InsertSort(int a[]) { for (int i = 1; i < n; i++) { int tmp = a[i], j = i - 1; while (j >= 0 && a[j]>tmp) { a[j + 1] = a[j]; --j; } a[j + 1] = tmp; echo(a); } } //6.Shell Sort void ShellSort(int a[]) { for (int pace = n/2; pace >= 1; pace/=2) { for (int i = pace; i < n; i++) { int tmp = a[i]; int j = i; while (j>=pace && tmp<a[j-pace]) { a[j] = a[j - pace]; j -= pace; } a[j] = tmp; echo(a); } } } //7.Merge Sort void merge(int a[], int left, int mid, int right) { if (a == nullptr || left > mid || mid > right) { return; } int i = left, j = mid + 1, len = right - left + 1; int* tmpMerge = new int[len]{ 0 }; int k = 0; while (i<=mid && j<=right) { if (a[i] < a[j]) { tmpMerge[k++] = a[i++]; } else { tmpMerge[k++] = a[j++]; } } while (i <= mid) { tmpMerge[k++] = a[i++]; } while (j <= right) { tmpMerge[k++] = a[j++]; } memcpy(&a[left], tmpMerge, len * sizeof(int)); delete[] tmpMerge; } void MergeSort(int a[], int left, int right) { if (a == nullptr || left >= right) { return; } int mid = (left + right) / 2; MergeSort(a, left, mid); MergeSort(a, mid + 1, right); merge(a, left, mid, right); echo(a); } int main() { cout << "Input numbers of array: "; while (cin>>n) { int* a = new int[n]; cout << "Input array: "; for (int i = 0; i < n; i++) { cin >> a[i]; } int* tmp = new int[n]; memcpy(tmp, a, n * sizeof(int)); cout << "Bubble Sort:" << endl; echo(a); BubbleSort(a); memcpy(a, tmp, n * sizeof(int)); cout << "Quick Sort:" << endl; echo(a); QuickSort(a, 0, n - 1); memcpy(a, tmp, n * sizeof(int)); cout << "Select Sort:" << endl; echo(a); SelectSort(a); memcpy(a, tmp, n * sizeof(int)); cout << "Heap Sort:" << endl; echo(a); HeapSort(a); memcpy(a, tmp, n * sizeof(int)); cout << "Insert Sort:" << endl; echo(a); InsertSort(a); memcpy(a, tmp, n * sizeof(int)); cout << "Shell Sort:" << endl; echo(a); ShellSort(a); memcpy(a, tmp, n * sizeof(int)); cout << "Merge Sort:" << endl; echo(a); MergeSort(a, 0, n - 1); delete[] tmp; delete[] a; cout << endl << "Input numbers of array: "; } return 0; }