排序复习_代码纯享

头文件

#pragma once
#include<iostream>
#include<vector>
#include<utility>
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::swap;//插入排序
//1、直接插入排序（稳定）
void InsertSort(vector<int>& v);
//2、希尔排序
void ShellSort(vector<int>& v);//选择排序
//1、直接选择排序
void SelectSort(vector<int>& v);
//2、堆排序
void HeapSort(vector<int>& v);//交换排序
//1、冒泡排序（稳定）
void BubbleSort(vector<int>& v);
//2、快速排序
void QuickSortTest(vector<int>& v);//归并排序（稳定）
void MergeSort(vector<int>& arr, int left, int right);//计数排序
void CountSort(vector<int>& v);void Print(vector<int>& v);

排序代码

#define  _CRT_SECURE_NO_WARNINGS
#include"sort.h"void Print(vector<int>& v) {for (int e : v) {cout << e << " ";}cout << endl;
}void InsertSort(vector<int>&v) {int n = v.size();for (int i = 0; i < n - 1; i++) {int end = i;int tmp = v[end + 1];while (end >= 0) {if (tmp < v[end]) {v[end + 1] = v[end];--end;}else {break;}}v[end + 1] = tmp;}
}void ShellSort(vector<int>& v) {int n = v.size();int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; ++i) {int end = i;int tmp = v[end + gap];while (end >= 0) {if (v[end] > tmp) {v[end + gap] = v[end];end = end - gap;}else {break;}}v[end + gap] = tmp;}}
}void SelectSort(vector<int>& v) {int n = v.size();int begin = 0, end = n - 1;while (begin < end) {int mini = begin;int maxi = end;for (int i = begin + 1; i < end; i++) {if (v[mini] > v[i]) {mini = i;}if (v[maxi] < v[i]) {maxi = i;}}swap(v[mini], v[begin]);if (maxi == begin) {maxi = mini;}swap(v[maxi], v[end]);++begin;--end;}
}void AdjustDown(vector<int>& v, int parent, int size) {int n = size;int child = parent * 2 + 1;while (child < n) {if (child + 1 < n && v[child + 1] > v[child]) {++child;}if (v[child] > v[parent]) {swap(v[child], v[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}void HeapSort(vector<int>& v) {int n = v.size();for (int i = (n - 2) / 2; i >= 0; i--) {AdjustDown(v, i, n);}int end = n - 1;while (end) {swap(v[0], v[end]);AdjustDown(v, 0, end);--end;}
}void BubbleSort(vector<int>& v) {int n = v.size();for (int j = 0; j < n; j++) {bool exchange = false;for (int i = 1; i < n - j; i++) {if (v[i] < v[i - 1]) {swap(v[i], v[i - 1]);exchange = true;}}if (exchange == false)break;}
}void QuickSort(vector<int>& v, int begin, int end) {if (begin >= end)return;int left = begin;int right = end;int key = begin;while (left < right) {while (left < right && v[right] >= v[key]) {right--;}while (left < right && v[left] <= v[key]) {left++;}swap(v[right], v[left]);}swap(v[key], v[left]);key = left;//begin  key  endQuickSort(v, begin, key - 1);QuickSort(v, key + 1, end);
}void QuickSortTest(vector<int>& v) {int n = v.size();int begin = 0;int end = n - 1;QuickSort(v, begin, end);
}// 合并两个已排序的子数组
void Merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组vector<int> L(n1), R(n2);// 拷贝数据到临时数组 L[] 和 R[]for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 归并临时数组到 arr[left..right]int i = 0; // 初始化第一个子数组的索引int j = 0; // 初始化第二个子数组的索引int k = left; // 初始归并子数组的索引while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;}else {arr[k] = R[j];j++;}k++;}// 拷贝 L[] 的剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}// 拷贝 R[] 的剩余元素while (j < n2) {arr[k] = R[j];j++;k++;}
}// 归并排序函数
void MergeSort(vector<int>& arr, int left, int right) {if (left < right) {// 找到中间点int mid = left + (right - left) / 2;// 递归排序左半部分MergeSort(arr, left, mid);// 递归排序右半部分MergeSort(arr, mid + 1, right);// 合并已排序的两部分Merge(arr, left, mid, right);}void CountSort(vector<int>& v) {int n = v.size();int max = v[0];int min = v[0];for (int i = 0; i < n; i++) {if (v[i] < min)min = v[i];if (v[i] > max)max = v[i];}int range = max - min + 1;vector<int> count(range, 0);//统计每个元素出现的次数for (int num : v) {++count[num - min];}//输出int j = 0;for (int i = 0; i < range; i++) {while (count[i]) {v[j] = i + min;j++;count[i]--;}}
}

测试排序代码

#define  _CRT_SECURE_NO_WARNINGS
#include"sort.h"int main() {vector<int> v = { 3,5,1,4,2,7,6 };Print(v);//InsertSort(v);//ShellSort(v);//SelectSort(v);//BubbleSort(v);//HeapSort(v);//QuickSortTest(v);MergeSort(v, 0, 6);Print(v);}