插入排序-----希尔排序---升级版插入

#include<iostream> using namespace std; void swap(int& a, int& b) { int temp = a; a = b; b = temp; } void print(int a[], int n) { printf("\n"); for (int i = 0; i < n; i++) { printf(" %d ", a[i]); } } //插入排序 void insertsort(int a[], int n) { for (int i = 1; i < n; i++) { int temp = a[i]; int j = i; while ((temp < a[j - 1]) && j>0) { a[j] = a[j - 1];//右移 j--; } a[j] = temp; } } void shell_sort1(int a[], int n)//希尔排序--也称为分组插入排序！！！！ { int i, j, gap; // gap为步长，每次减为原来的一半。 for (gap = n / 2; gap > 0; gap /= 2)//回合 { // 共gap个组，对每一组都执行直接插入排序 for (i = 0; i < gap; i++)///组数 { for (j = i + gap; j < n; j += gap)//相当于 for (int i = 1; i < n; i++) { // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。 int tmp = a[j]; int k = j-gap; while (k >= 0 && a[k] > tmp)// while ((temp < a[j - 1]) && j>0) { a[k+gap] = a[k]; k -= gap; } a[k+gap] = tmp; } } } } int main() { int a[20] = { 0, 1, 17, 3, 4, 5, 13, 18, 11, 9, 10, 8, 12, 6, 14, 15, 16, 2, 7, 19 }; shell_sort1(a,20); print(a,20); return 0; }