常见排序算法

常见排序算法

void swap (vector &a, int i, int j) { int idx = a[i]; a[i] = a[j]; a[j] = idx;}//冒泡排序void bubbleSort(vector &a) { int n = a.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); } } }}//选择排序void selectSort(vector &a) { int n = a.size(); int mini = 0; for (int i = 0; i < n - 1; i++) { mini = i; for (int j = i + 1; j < n; j++) { if (a[mini] > a[j]) { mini = j; } } swap(a, mini, i); }}//插入排序void insertSort(vector &a) { int n = a.size(); int temp = 0; for (int i = 1; i < n; i++) { int j = i; temp = a[i]; while (j > 0 && temp < a[j - 1]) { a[j] = a[j - 1]; j--; } a[j] = temp; }}//递归快速排序void quickSort(vector &a, int low, int high) { if (low >= high) { return; } int left = low, right = high; int value = a[low]; while (left < right) { while (left < right && a[left] < value) { left++; } if (left < right) { a[right] = a[left]; right--; } while (left < right && a[right] >= value) { right--; } if (left < right) { a[left] = a[right]; left++; } } a[left] = value; quickSort(a, low, left - 1); quickSort(a, left + 1, high);}//非递归快速排序void quickSort2(vector &a) { stack > stk; int low = 0, high = a.size() - 1; stk.push(make_pair(low, high)); while (stk.empty() == false) { int i = stk-().first; int j = stk-().second; stk.pop(); int value = a[i]; int left = i, right = j; while (i != j) { while (i < j && a[i] < value) { i++; } while (i < j && a[j] > value) { j--; } swap(a, i, j); } if (i < right) { stk.push(make_pair(i + 1, right)); } if (i > left) { stk.push(make_pair(left, i - 1)); } }}//递归二路归并排序void mergeSort(vector &a, vector &b, int first, int last) { if (first < last) { int mid = first + (last - first) / 2; mergeSort(a, b, first, mid); mergeSort(a, b, mid + 1, last); int i = first, j = mid + 1, k = first; while (i <= mid && j <= last) { if (a[i] < a[j]) { b[k++] = a[i++]; } else { b[k++] = a[j++]; } } while (i <= mid) { b[k++] = a[i++]; } while (j <= last) { b[k++] = a[j++]; } for (int i = first; i <= last; i++) { a[i] = b[i]; } }}//堆排序void adjustHeap(vector &a, int i, int k) { int data = a[i]; for (int j = i * 2 + 1; j < k; j = j * 2 + 1) { int left = j, right = j + 1; if (right < k && a[left] < a[right]) { j++; } if (data < a[j]) { a[i] = a[j]; i = j; } else { break; } } a[i] = data;}void heapSort(vector &a) { int n = a.size(); int k = n - 1; for (int i = n / 2 - 1; i >= 0; i--) { adjustHeap(a, i, n); } for (int i = 0; i < n; i++) { cout << a[i] << " "; } while (k > 0) { swap(a, 0, k); adjustHeap(a, 0, k); k--; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。