以下是一些插入排序的代码
1.插入排序
1.直接插入排序
// 升序
// 最坏：O(N^2) 逆序
// 最好：O(N) 顺序有序
void InsertSort(vector<int>& a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];// 将tmp插入到[0,end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}
//一个一个插入 一个 一个排序2.折半插入排序
折半插入排序本质上就是 插入排序 ＋二分查找
// 折半插入排序函数
void binaryInsertionSort(std::vector<int>& arr) {int n = arr.size();for (int i = 1; i < n; ++i) {int key = arr[i];int left = 0, right = i - 1;// 二分查找插入位置while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > key) {right = mid - 1;}else {left = mid + 1;}}// 将元素后移for (int j = i - 1; j >= left; --j) {arr[j + 1] = arr[j];}// 插入元素arr[left] = key;}
}3.希尔排序
//希尔排序
void ShellSort(vector<int>&a, int n)
{/*int gap = 3;for (int j = 0; j < gap; j++){for (int i = j; i < n - gap; i += gap){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}*/// gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){//gap /= 2;gap = gap / 3 + 1;//除2是不用＋1的 因为你能保证最后gap一定是1 gap为1就是直接插入排序 但是/3就不能保证了！for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}//PrintArray(a, n);}
}希尔排序的这两种实现方式的时间复杂度是一模一样的 只是遍历的方式不一样
2.选择排序
1.直接选择排序
void Swap(int& a, int& b) {int temp = a;a = b;b = temp;
}// 直接选择排序函数
void SelectSort(int* a, int n) {for (int i = 0; i < n - 1; ++i) {int minIndex = i;for (int j = i + 1; j < n; ++j) {if (a[j] < a[minIndex]) {minIndex = j;}}if (minIndex != i) {Swap(a[i], a[minIndex]);}}
}可以对其进行优化 比如我一次选两个数出来
但是这个时候swap的时候要确认一下特殊情况
同时如果是有序的就可以直接break了 不用那么麻烦
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false){break;}}
}2.堆排序
// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 自己先实现 -- O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}3.交换排序
1.冒泡排序
//冒泡排序// 最坏：O(N^2)
// 最好：O(N)
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false){break;}}
}