/* * incremental sorting */ voidInsertSort(vector<int> &nums){ for (int i = 1; i < nums.size(); ++i) { if (nums[i] < nums[i - 1]) { // if the 最坏情况下,如上图,希尔排序优于其他插入排序。
而当数据全都是已排序状态时,希尔排序不如其他插入排序。current number is less than the number before it, int temp{nums[i]}, j{0}; // store the current number with a temporary variable for (j = i - 1; j >= 0 && temp < nums[j]; --j) { nums[j + 1] = nums[j]; } nums[++j] = temp; } } }
intmain(){ vector<int> nums{2, 6, 4, 24, 6, 8, 25, 34}; InsertSort(nums); for (int i : nums) { cout << i << "\t"; } cout << endl; return0; }
/* * incremental sorting * optimized */ voidInsertSort(vector<int> &nums){ for (int i = 2; i < nums.size(); ++i) { int low{0}, high{i - 1}, temp{nums[i]}; while (low <= high) { int mid{int((low + high) / 2)}; // if mid == temp, we still cannot insert temp after mid! because we don't know how many items are repeated // for example,[1,2,2,2,3...],while we compare number 2 with the third number 2,they are equal, // but we cannot insert number 2 into the place after the third number 2,because the stability is compromised if (temp < nums[mid]) { high = mid - 1; } else { low = mid + 1; } }
/* * incremental sorting */ voidInsertSort(vector<int> nums){ for (int i = 1; i < nums.size(); ++i) { if (nums[i] < nums[i - 1]) { // if the current number is less than the number before it, int temp{nums[i]}, j; // store the current number with a temporary variable for (j = i - 1; j >= 0 && temp < nums[j]; --j) { nums[j + 1] = nums[j]; } nums[++j] = temp; } } }
/* * incremental sorting * optimized */ voidInsertSortOptimized(vector<int> nums){ for (int i = 2; i < nums.size(); ++i) { int low{0}, high{i - 1}, temp{nums[i]}; while (low <= high) { int mid{int((low + high) / 2)}; // if mid == temp, we still cannot insert temp after mid! because we don't know how many items are repeated // for example,[1,2,2,2,3...],while we compare number 2 with the third number 2,they are equal, // but we cannot insert number 2 into the place after the third number 2,because the stability is compromised if (temp < nums[mid]) { high = mid - 1; } else { low = mid + 1; } }