希尔排序是直接插入排序的改良版,因为直接插入排序在数组基本有序的时候(或则说每个值都快要接近正确位置时),排序效率最高,希尔排序就是为了通过分组的方式,使得待排序数组基本有序。当希尔排序步长为1时就是直接插入排序了。
#includeusing namespace std; void ShellSort(int arr[], int n); int main() { int arr[] = {25, 6, 23, 52, 1, 3, 5, 9, 6, 112}; ShellSort(arr, 10); return 0; } void ShellSort(int arr[], int n) { for (int d = n / 2; d >= 1; d = d / 2) { //外层增量,增量的数值依次为整个数组长度的1/2,1/4,......,进行减小。 for (int i = d; i < n; ++i) { int t = arr[i]; int j = i - d; //将所分割出的一组数组进行直接插入排序 while (j >= 0 && t < arr[j]) { arr[j + d] = arr[j]; j = j - d; } arr[j+d] = t; } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)