直接插入排序与希尔排序

2019-11-06 06:56:58

字体：大中小

来源：转载

供稿：网友

直接插入排序原理：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素中的适当位置处，直到元素全部插入为止。（简单来说就是将无序区的元素，插入到有序区内，找到适当插入位置，并且将其后所有元素后移）

实现步骤： 1>我们可以将第一个元素看作有序序列，将后面元素看作无序序列，从头到尾依次扫描未排序序列，给无序区的元素找到适当插入位置，将其位置后所有元素后移，然后流出空位进行插入。可以配合图解来理解: 这里写图片描述

#include<iostream>using namespace std;template<class T> struct Less //降序的仿函数{ bool Operator()(const T& s, const T& l) { return s < l; }};template<class T> //升序的仿函数struct Greater{ bool operator()(const T&s, const T& l) { return s > l; }};template<class T=int,class Compare=Greater<T>>//默认升序排序void InsertSort(T* arr, size_t size){ int pos = 0; Compare com; for (size_t i = pos+1; i < size; ++i) { pos = i - 1; T ret = arr[i]; while (pos>=0&&com(arr[pos],ret)) { arr[pos+1] = arr[pos]; --pos; } arr[pos+1] = ret; }}void TestInsert(){ int arr[] = { 3, 6, 4, 2, 11, 10, 5 }; InsertSort<int>(arr, sizeof(arr) / sizeof(arr[0]));}

直接插入排序完成了，我们来看看这个排序最好和最坏的情况，最坏的情况莫过于逆序,而最好的情况就是有序的。所以越接近有序效率越高，于是之后便有了希尔排序 2. 希尔排序希尔排序呢，其实还是插入排序的思想，只是将插入排序分解成gap个子序列，所有距离为gap的元素放在同一个子序列中，在给每一个序列分别进行插入排序。然后缩小间隔gap，例如gap=gap/3+1，重复上面操作，当gap==1时就相当于分了一个序列，这时的序列已经基本有序，所以排序速度依然很快。

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;template<class T>struct Less //降序的仿函数{ bool operator()(const T& s, const T& l) { return s < l; }};template<class T> //升序的仿函数struct Greater{ bool operator()(const T&s, const T& l) { return s > l; }};template<class T = int, class Compare = Greater<T>>void ShellSort(T* arr,int size){ int gap = size; Compare com; while (gap > 1) { gap = gap / 3 + 1; int pos = 0; for (int i = pos + gap; i < size; ++i) { T tmp = arr[i]; pos = i - gap; while (pos >= 0 && com(arr[pos],tmp)) { arr[pos + gap] = arr[pos]; pos -= gap; } arr[pos + gap] = tmp; } }}void Shelltest(){ int arr[] = { 7, 8, 2, 5, 7, 9, 3, 1, 4, 6, 2, 0, 11, 5, 14 }; ShellSort<int>(arr, sizeof(arr) / sizeof(arr[0]));}

上一篇：Codeforces #403 Div.2 B.The Meeting Place Cannot Be Changed

下一篇：Codeforces Round #403 (Div. 2) B. The Meeting Place Cannot Be Changed

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注