插入排序(直接插入排序,折半插入排序,希尔排序)

插入排序(直接插入排序,折半插入排序,希尔排序)目录 1 直接插入排序 1 1 从前往后插入 1 2 从后往前插入 图略 2 折半排序 3 希尔排序 3 1 从前往后插入 3 2 从后往前插入 图略 1 直接插入排序 1 1 从前往后插入 include iostream using iostream

大家好,我是讯享网,很高兴认识大家。

目录

1.直接插入排序

1.1从前往后插入

1.2从后往前插入 (图略)

2.折半排序 

3.希尔排序

3.1 从前往后插入 

 3.2从后往前插入(图略)



讯享网

1.直接插入排序

1.1从前往后插入

#include<iostream> using namespace std; int main() { int n; cin >> n; int* a = new int[n];//动态分配一维数组 for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++)//循环趟数 { if (a[i] < a[i - 1])//可以减少部分时间 { int key = a[i];//选择要插入的数字key int j = i - 1; while (key < a[j] && j >= 0)//将key前面大于key的数字往后移 { a[j + 1] = a[j]; j--; } a[j + 1] = key;//插入空位 } } for (int i = 0; i < n; i++) { if (i) cout << " " << a[i]; else cout << a[i]; } }

讯享网

1.2从后往前插入 (图略)

讯享网for (i = n-2; i >=0; i--)//循环趟数 { if (a[i] > a[i + 1])//可以减少部分时间 { int key = a[i];//选择要插入的数字key j = i+1 ; while (key > a[j] && j <n)//将key后面小于key的数字往前移 { a[j - 1] = a[j]; j++; } a[j - 1] = key;//插入空位 } }

2.折半排序 

 

 代码如下:

#include<iostream> using namespace std; int main() { int n,i,j; cin >> n; int* a = new int[n];//动态分配一维数组 for (int i = 0; i < n; i++) { cin >> a[i]; } for (i = 1; i < n; i++)//循环趟数 { if (a[i] < a[i - 1])//可以减少部分时间 { int key = a[i];//选择要插入的数字key int low = 0, high = i-1;//切记high=i-1不是i while (low <= high) { int mid = (low + high) / 2;//取中间位置 if (key < a[mid])//也可以用<=,没关系 high = mid - 1;//插入点在左半区 else low = mid + 1;//插入点在右半区 } for (j = i - 1; j >= high + 1; j--)//将key前面大于key的数字往后移 a[j + 1] = a[j]; a[j + 1] = key;//插入空位即high+1位置 } } for (i = 0; i < n; i++) { if (i) cout << " " << a[i]; else cout << a[i]; } }

3.希尔排序

3.1 从前往后插入 

讯享网#include<iostream> using namespace std; int main() { int n; cin >> n; int* a = new int[n];//动态分配一维数组 for (int i = 0; i < n; i++) { cin >> a[i]; } int d = n / 2;//增量初始值 while (d > 0) { for (int i = d; i < n; i++)//每一次增量时循环趟数 { if (a[i] < a[i - d])//可以减少部分时间 { int key = a[i];//选择要插入的数字key int j = i - d; while (key < a[j] && j >= 0)//将key前面大于key的相隔d的数字往后移 { a[j + d] = a[j]; j -= d; } a[j + d] = key;//插入空位 } } d /= 2;//减小增量 } for (int i = 0; i < n; i++) { if (i) cout << " " << a[i]; else cout << a[i]; } }

 3.2从后往前插入(图略)

int d = n / 2; while (d > 0) { for (i = n - 1 - d; i >= 0; i--)//每一次增量时循环趟数 { if (a[i] > a[i + d])//可以减少部分时间 { int key = a[i];//选择要插入的数字key j = i + d; while (key > a[j] && j < n)//将key后面小于key的相隔d的数字往前移 { a[j - d] = a[j]; j += d; } a[j - d] = key;//插入空位 } } d /= 2; }

小讯
上一篇 2025-03-10 16:07
下一篇 2025-02-19 14:06

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81994.html