排序算法03-插入排序

排序算法03-插入排序

一、简单插入排序

数组的红色部分是有序部分，每次取无序部分（黑色部分）的第一个元素插入到有序部分的合适位置。插入后，有序部分元素多一个。

把每个元素往前插入时，先用数组的0号元素记下此待排序元素，然后在前面寻找合适的位置插入寻找合适的位置时，若当前位置不合适，则记下当前遍历元素的下标，并往后移当前元素不大于待排序元素时则找到合适的位置

图解：

以对 [3,1,4,2,7,5] 六个元素排序为例

/** * @author Leo * 时间复杂度为O(n^2) */ void InsertSort(vector& nums){ int pos; //对1~n号元素进行排序，首先1号元素本身有序，从2号元素开始往前插入 for(int i = 2; i < nums.size(); i++){ if(nums[i] < nums[i - 1]){ nums[0] = nums[i];//将0号元素设置成待排序元素 int j = i - 1;//j索引用于往前遍历 while(nums[j] > nums[0]){ nums[j + 1] = nums[j]; pos = j;//记录可能插入的位置 j--; } nums[pos] = nums[0];//当此时遍历的元素不大于待插入元素时，找到合适的插入位置 } }}

二、希尔排序

图解：

以对 [3,1,4,2,7,5,6] 七个元素排序为例

每个组内进行插入排序，组内插入排序的结果如下：

在编程实现中，插入的顺序是按照索引顺序的：

2. gap = 1，此时就和上面介绍的简单插入排序一模一样了

排序结果如下：

/** * 希尔排序就是改变步长的插入排序 * 由于拆成多部分操作，若存在相同元素，被划分为不同部分后 * 值相同的元素之间没有联系，故希尔排序不稳定 */ void ShellSort(vector& nums){ int pos;//记录待排序元素可能插入的位置 int gap = nums.size() / 2; while(gap >= 1){ //每一次for循环结束，都将每个gap的排序工作完成（依然从1号元素开始排序） for(int i = gap + 1; i < nums.size(); i++){ if(nums[i] < nums[i - gap]){ nums[0] = nums[i];//记录待插入元素 int j = i - gap; //while循环用于寻找合适位置 while(nums[j] > nums[0] && j > 0){ pos = j; nums[j + gap] = nums[j]; j -= gap; } nums[pos] = nums[0];//while循环结束，找到合适位置，插入 } } gap >>= 1;//折半 }}

归并排序

//聚合部分 void merge(vector& nums, int left, int mid, int right){ int count = right - left + 1; vector temp(count, 0); int i = left;//一数组的开头 int j = mid + 1;//另一数组的开头 int k = 0;//大数组的开头 while(i <= mid && j <= right){ if(nums[i] < nums[j]){ temp[k] = nums[i]; k++; i++; }else{ temp[k] = nums[j]; k++; j++; } } while(i <= mid){ temp[k] = nums[i]; k++; i++; } while(j <= right){ temp[k] = nums[j]; k++; j++; } for(int index = 0; index < count; index++){ nums[index + left] = temp[index]; } } //递归分治部分 void mergeSort(vector& nums, int left, int right){ if(left < right){ int mid = (left + right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, mid, right); } } vector sortArray(vector& nums) { mergeSort(nums, 0, nums.size() - 1); return nums; }

排序算法的比较

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。