以下是一些插入排序的代碼
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;}}
}
)
