北京西站出站口,电子商务网站是电子商务企业,google下载官网,龙岗网站-建设深圳信科01 插入排序(Insertion Sort) 原理#xff1a;每次选择一个元素#xff0c;并且将这个元素和整个数组中的所有元素进行比较#xff0c;然后插入到合适的位置。 void insertion_sort(int arr[], int n)
{int i,j;for (i 1; i n; i) {int tmp arr[i];for (j i; j … 01 插入排序(Insertion Sort) 原理每次选择一个元素并且将这个元素和整个数组中的所有元素进行比较然后插入到合适的位置。 void insertion_sort(int arr[], int n)
{int i,j;for (i 1; i n; i) {int tmp arr[i];for (j i; j 0 arr[j - 1] tmp; j--) {arr[j] arr[j - 1];}arr[j] tmp;}
} 空间效率O(1) 时间效率最好情况O(n) 平均情况O(N^2) 最坏情况O(N^2) 稳定性相同元素相对位置变化情况稳定 适用性顺序存储的线性表 注还有个折半插入排序其原理就是查找插入位置时从中间开始找起。 02 希尔排序Shell Sort 这个是插入排序的修改版根据步长由长到短分组进行排序直到步长为1为止属于插入排序的一种。 //希尔排序-希尔增量
void shell_sort(int arr[], int n) {int j;for (int d n / 2;d 0;d / 2) {for (int i d;i n;i) {int temp arr[i];for (j i;j d arr[j - d] temp;j - d)arr[j] arrj - d];arr[j] temp;}}
} //希尔排序-sedgewick增量
void shellsedgewick_sort(int arr[], int n) {int i, j, d, si;int Sedgewick[] { 929, 505, 209, 109, 41, 19, 5, 1, 0 };for (si 0;Sedgewick[si] n;si);for (;Sedgewick[si] 0;si) {d Sedgewick[si];for (i d;i n;i) {int temp arr[i];for (j i;j d arr[j - d] temp;j - d)arr[j] arr[j - d];arr[j] temp;}}
} 空间效率O(1) 时间效率依赖于增量序列的函数 当n在一个特定范围内时复杂度为O(^1.3) 最坏情况O(N^2) 稳定性相同元素相对位置变化情况不稳定 适用性顺序存储的线性表 转载于:https://www.cnblogs.com/wanghao-boke/p/10415706.html
