目录
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; }

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