C++插入排序 包括折半插入排序法代码，在直接插入排序,数组data用于存放待排序元素，n为待排序元素个数，同时还包括了对data数组中的元素进行希尔排序，n为该数组大小等：
| 代码如下 | 复制代码 |
| #include <iostream> using namespace std; #include "sort.h" // 直接插入排序,数组data用于存放待排序元素，n为待排序元素个数 template<class ElemType> void InsertSort(ElemType data[], int n) { ElemType tmp; int i, j; for (i = 1; i < n; i++){ if ( data[i] > data[i - 1]) continue; tmp = data[i]; // 保存待插入的元素 data[i] = data[i - 1]; for ( j = i - 1; j > 0 && data[j - 1] > tmp;j--) data[j] = data[j - 1]; // 元素后移 data[j] = tmp; // 插入到正确位置 } } // 折半插入排序 template<class ElemType> void BInsertSort(ElemType data[], int n) { ElemType tmp; int i, j, mid, low, high; for (i = 1; i < n; i++){ tmp = data[i]; // 保存待插入的元素 low = 0; high = i-1; while (low <= high){ // 在data[low..high]中折半查找有序插入的位置 mid = (low + high) / 2; // 折半 if( tmp < data[mid]) high = --mid; // 插入点在低半区 else low = ++mid; // 插入点在高半区 } for(j = i - 1; j >= low; j--) data[j + 1] = data[j]; // 元素后移 data[low] = tmp; // 插入到正确位置 } } // 对data数组中的元素进行希尔排序，n为该数组大小 // increments为增量序列，incrementsLength为增量序列的大小 template<class ElemType> void ShellSort(ElemType data[], int increments[], int n, int incrementsLength) { int i, j, k; ElemType tmp; for ( k = 0; k < incrementsLength; k++){ // 进行以increments[k]为增量的排序 for ( i = increments[k]; i < n; i++){ tmp = data[i]; for ( j = i; j >= increments[k]; j -= increments[k]){ if ( tmp >= data[j - increments[k]]) break; data[j] = data[j - increments[k]]; } data[j] = tmp; } } } |
|
补充一个
1.直接插入排序；2.折半插入排序；3.Shell排序；4.冒泡排序；5.快速排序；6.简单选择排序；7.堆排序；8.2-路归并排序；9.2-路归并排序（非递归）；10.基数排序等，程序代码如下：
| 代码如下 | 复制代码 |
|
#include "sort.h" int main() { cout << "---此程序实现排序---" << endl << endl; cout << "1.直接插入排序；2.折半插入排序；3.Shell排序；" << endl; cout << "4.冒泡排序；5.快速排序；" << endl; cout << "6.简单选择排序；7.堆排序；" << endl; cout << "8.2-路归并排序；9.2-路归并排序（非递归）；10.基数排序；" << endl; cout << "0.退出" << endl << endl; int n,select,*pData = NULL; SLList list; int* increments; while (true){ cout << "请选择排序算法：" << endl; cin >> select; switch ( select){ case 1: n = init(&pData); InsertSort(pData,n); break; case 2: n = init(&pData); BInsertSort(pData,n); break; case 3: int incrementsLenth,i; cout << "请输入增量序列长度：" << endl; cin >> incrementsLenth; increments = new int[incrementsLenth]; cout << "请输入增量序列：" << endl; for (i = 0; i < incrementsLenth; i++) cin >> increments[i]; n = init(&pData); ShellSort( pData,increments,n,incrementsLenth); delete[] increments; break; case 4: n = init(&pData); BubbleSort(pData,n); break; case 5: n = init(&pData); QuickSort(pData,n); break; case 6: n = init(&pData); SelectionSort(pData,n); break; case 7: n = init(&pData); HeapSort(pData,n); break; case 8: n = init(&pData); MergeSort(pData,n); break; case 9: n = init(&pData); MergeSortNonRecursion(pData, n); break; case 10: n = init(&pData); list.Init(pData,n); list.RadixSort(); list.Arrange(); break; // RadixSort(pData,n); // break; case 0: system("pause"); return 0; default: cout << "Input Error！"<< endl << endl; continue; } cout << "排序结果为：" << endl; if(select == 10) cout << list; else print( pData,0,n - 1); cout << endl; delete[] pData; } system("pause"); return 0; } int init(int** pData) { int size,i; cout << "输入待排序元素个数" << endl; cin >> size; *pData = new int[size]; cout << "输入待排序元素"<< endl; for(i = 0 ; i < size; i++) cin >> (*pData)[i]; return size; } template<class ElemType> void print(ElemType data[],int begin,int end) { for (int i = begin; i <= end; i++){ cout << data[i] << " "; } cout << endl; } |
|
时间： 2024-10-01 17:01:20