传奇网站模板怎么做的吗,如何查看网站做没做竞价,c2c网站开发毕业设计,app教程十大排序 —— 希尔排序 什么是希尔排序插入排序希尔排序递归版本 我们今天来看另一个很有名的排序——希尔排序
什么是希尔排序
希尔排序#xff08;Shell Sort#xff09;是插入排序的一种更高效的改进版本#xff0c;由Donald Shell于1959年提出。它通过比较相距一定间… 十大排序 —— 希尔排序 什么是希尔排序插入排序希尔排序递归版本 我们今天来看另一个很有名的排序——希尔排序
什么是希尔排序
希尔排序Shell Sort是插入排序的一种更高效的改进版本由Donald Shell于1959年提出。它通过比较相距一定间隔的元素来工作间隔会逐步减小直到最后变成1此时算法实际上退化为普通的插入排序但因为数组元素基本已经部分排序所以插入排序在这个阶段会非常高效。
希尔排序的基本思想是将原始数据集分割成若干子序列先使这些子序列基本有序然后再对全体记录进行一次直接插入排序。这里的基本有序是指在子序列内任意两个元素之间的距离都不超过某个预先设定的间隔称为增量或gap时它们的顺序要么是正确的要么仅需很少的比较和移动就可以变得正确。
希尔排序的具体步骤如下 选择一个增量序列首先确定一个增量gap常见的选择有希尔增量如gap gap / 2直到gap 1或者使用更复杂的序列如Hibbard增量序列。分组排序将整个数组分成多个子序列每个子序列包含相距gap的元素然后对每个子序列应用插入排序。减小增量重复步骤1和2但每次减小增量的大小直到增量为1。最终排序当增量减至1时整个数组就是一个子序列对这个子序列执行插入排序这时数组应该是或接近完全有序。 希尔排序的优势在于它能够较早地将远处的元素移动到更接近其最终位置从而减少了数据移动的总次数提高了排序效率。特别是在数组规模较大时相比简单的插入排序希尔排序能显著提高排序速度。希尔排序的时间复杂度依赖于所选的增量序列最好的情况可以达到O(n log n)最坏情况则与所选增量序列有关但通常优于O(n^2)。
再讲希尔排序之前我们讲一下插入排序。
插入排序
插入排序Insertion Sort是一种简单直观的排序算法适用于对小型数据集合或者基本有序的数据集合进行排序。它的核心思想是将一个记录或数据元素插入到已经排序好的有序表中从而得到一个新的、记录数增加1的有序表。
插入排序的基本步骤如下 初始化假设数组的第一个元素已经被排序。遍历数组从第二个元素开始每次取出一个元素记为key在已排序序列中从后向前扫描。比较与移动如果该元素key小于它前面的元素则将前面的元素向后移动一位为key腾出位置否则停止扫描。插入元素将key插入到已排序序列中的适当位置即找到的正确位置或扫描停止的位置。重复步骤2-4对数组中的每个元素都执行这样的插入操作直到数组完全排序。 插入排序的时间复杂度分析 最好情况当输入数组已经是排序状态时插入排序只需要进行n-1次比较不需要移动数据时间复杂度为O(n)。最坏情况当输入数组是反序时每次插入都相当于在数组的最前面插入每次插入操作需要移动所有的已排序元素时间复杂度为O(n^2)。平均情况对于随机数据插入排序的时间复杂度也是O(n^2)。 插入排序的空间复杂度为O(1)因为它是一种原地排序算法除了输入数组外只需要常数级别的额外空间用于交换和临时存储。此外插入排序是稳定的排序算法即相等的元素的相对顺序不会改变。
画个图就是这样的
// 选择插入排序函数实现
void select_sort(int *array, int size)
{// 遍历整个数组除了最后一个元素因为它自然有序for (int i 0; i size - 1; i){// 选取当前位置i1的元素作为待插入元素int temp array[i 1];// 初始化已排序部分的最后一个元素索引int end i;// 当已排序部分的索引大于等于0时进入循环while (end 0){// 如果已排序部分的当前元素大于待插入元素if (array[end] temp){// 将较大的元素向后移动一位为待插入元素腾出空间std::swap(array[end 1], array[end]);// 缩小已排序部分的范围继续向前比较end--;}else{// 如果当前元素不大于待插入元素说明找到了temp的正确位置// 或者已经检查到数组起始此时无需再比较直接跳出循环break;}}}// 循环结束数组完成排序
}int main()
{int array[] { 1,34,56,1,233,56,0 };for (auto e : array){std::cout e ;}std::cout std::endl;select_sort(array, sizeof(array) / sizeof(array[0]));for (auto e : array){std::cout e ;}
}大家可以画个图结合着图能比较清晰理解。
希尔排序
我们已经了解到了希尔排序的特殊形式直接插入排序现在我们来了解一下更一般的形式希尔排序。 我们之前用直接插入排序来让数据升序排列我们来考虑一下它最糟糕的情况数据是降序排序的。 这样的话9之后的数据都要进行一次插入插入到9之前时间复杂度可以达到O(N2)但我们会遇到这样一种情况 10比9大故不用进行插入了而我们可不可以让这种情况更普遍一些呢所以我们可以在进行排序之前先进行一次预排序让数据整体是升序的这就是希尔排序。 希尔排序的步骤 将数据分成gap组。以gap为间隔进行直接插入排序。 //希尔排序
void ShellSort(int* a, int n)
{assert(a);int gap 3;for (int i 0; i n - gap ; igap){int end i;int temp a[end gap];while (end 0){if (temp a[end]){std::swap(array[end gap], array[end]);end-gap;}else{break;}}}
}
这段代码的结果是什么样的呢我们来画图看看 其实我们只完成了一组红色数据的预排序其实我们的预排序可以不止一组 那么如何完成这三组的排序呢很简单加一层for循环。
//希尔排序
void shell_sort(int* array, int size)
{int gap 3;for (int j 0; j 3; j){for (int i j; i size - gap; i gap){//后面一个待排元素int temp array[i gap];int end i;while (end 0){if (array[end] temp){std::swap(array[end gap], array[end]);end-gap;}else{break;}}}}}
我们看看程序结果怎么样 我们发现数据的排序是有一些变化但好像还是有点混乱这是因为gap的原因这时候我们把gap改为2看看 我们发现gap越大数据排序越混乱但移动的越快**gap越小数据越有序但移动的越慢**这直接和时间复杂度有关。
// 希尔排序函数实现
void shell_sort(int* array, int size)
{// 初始化间隔(gap)为数组的长度int gap size;// 当间隔大于1时持续执行以下步骤逐步减小间隔以达到排序效果while (gap 1){// 计算新的间隔这里使用的是一个简化的规则将间隔除以3并加1这是一种常用的递减策略gap gap / 3 1;// 这个循环是为了处理不同子序列的起始位置确保每个间隔下的元素都能被遍历到for (int j 0; j gap; j){// 遍历数组从当前子序列的起始位置开始步长为当前的间隔for (int i j; i size - gap; i gap){// 保存当前间隔位置的下一个元素准备进行插入排序int temp array[i gap];int end i;// 内部循环实现插入排序逻辑将temp插入到已排序的子序列中正确的位置while (end 0){// 如果当前子序列中的元素大于temp将该元素后移if (array[end] temp){std::swap(array[end gap], array[end]); // 交换元素end - gap; // 移动到前一个位置继续比较}else{// 如果找到了temp的正确位置或已经比较到子序列的起始位置跳出循环break;}}}}}// 当所有间隔遍历完成后数组已经基本排序完成由于最后一次gap为1实质上进行了最后一次的插入排序收尾
}
其实这段代码还有一个变形也可以达到效果多组并排
//希尔排序
void shell_sort(int* array, int size)
{int gap size;while (gap 1){gap gap / 3 1;for (int i 0; i size - gap; i ){//后面一个待排元素int temp array[i gap];int end i;while (end 0){if (array[end] temp){std::swap(array[end gap], array[end]);end - gap;}else{break;}}}}
}递归版本
这里实现递归版本完全是为了锻炼思维实际中不会这样写仅供参考
void select_sort(int* array, int size, int index)
{ // 如果index小于0递归结束 if (index 0) return; // 递归调用先对前面的部分进行排序 select_sort(array, size, index - 1); // 如果index已经是最后一个元素或者超过最后一个元素的索引则不需要再进行排序 if (index size - 1) return; // 临时存储index1位置的元素这个元素可能是当前未排序部分的最小值 int temp array[index 1]; int end index; // 从index位置开始向前比较 // 这是一个插入排序Insertion Sort的插入过程但逻辑上不适合选择排序 while (end 0) { // 如果当前元素比temp大则将当前元素后移 if (array[end] temp) { std::swap(array[end], array[end 1]); end--; } else { // 如果找到合适的位置或者已经到达数组的开头就跳出循环 break; } } }希尔排序
// 递归实现的插入排序用于希尔排序中每轮的细分排序
void select_sort(int* array, int size, int index, int gap)
{// 递归基础情况当索引小于0时说明已处理完当前gap下的所有元素if (index 0)return;// 递归调用处理当前元素前一个gap位置的元素逐步向前select_sort(array, size, index - gap, gap);// 防止数组越界当索引达到size-gap时说明当前gap下已无更多元素需要处理if (index size - gap)return;// 保存当前gap位置的元素值准备进行插入排序int temp array[index gap];int end index;// 插入排序逻辑将temp插入到前方已排序的子序列中的正确位置while (end 0){if (array[end] temp){// 交换元素将较大的元素后移为temp腾出位置std::swap(array[end gap], array[end]);end - gap; // 更新索引继续向前比较}else{// temp已到达或超过其正确位置停止循环break;}}
}// 实现希尔排序的主体函数使用递归的select_sort进行每一轮的细分排序
void shell_sort(int* array, int size, int index)
{int gap size;// 循环直到gap减至1每轮使用一个较小的gap进行插入排序while (gap 1){ // 计算下一轮的gap值这里采用gap gap / 3 1是一种常见但非唯一的策略gap gap / 3 1;// 使用当前gap值调用select_sort进行插入排序select_sort(array, size, index, gap);}
}
