最新的网站建设软件有哪些,手机站点,中山做网站公司,外国网站架构排序算法 —— 希尔排序
算法介绍
希尔排序#xff08;Shell Sort#xff09;是一种基于插入排序的算法#xff0c;由Donald Shell于1959年提出。希尔排序的基本思想是将待排序的序列划分成若干个子序列#xff0c;分别进行插入排序#xff0c;待整个序列中的记录基本有…排序算法 —— 希尔排序
算法介绍
希尔排序Shell Sort是一种基于插入排序的算法由Donald Shell于1959年提出。希尔排序的基本思想是将待排序的序列划分成若干个子序列分别进行插入排序待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
算法基本思想
基本概念
间隔序列希尔排序中间隔序列是一个递减的序列用于控制子序列的划分。初始间隔较大逐步减小最终减至1此时整个序列被视为一个子序列。子序列根据间隔序列将原始序列划分成若干个子序列每个子序列中的元素间隔为当前间隔序列中的数值。
算法步骤
选择一个间隔序列 ( G_1, G_2, …, G_t )其中 ( G_t 1 )。根据当前间隔 ( G_i )将序列分成若干子序列对每个子序列进行插入排序。减小间隔 ( G_{i1} )重复步骤2直至间隔为1此时整个序列被视为一个子序列进行最后一次插入排序。
伪代码描述
function shellSort(arr):n length(arr)gap n / 2while gap 0:for i gap; i n; i:temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap gap / 2return arr优点
效率提升希尔排序比传统的插入排序在效率上有显著提升特别是当数据量较大时。减少移动次数通过比较距离较远的元素希尔排序减少了元素之间的比较和移动次数从而提高了排序效率。灵活性希尔排序的间隔序列可以灵活选择不同的间隔序列可能会带来不同的性能表现。易于实现希尔排序的算法实现相对简单理解和实现起来比较容易。
缺点
时间复杂度在最坏的情况下希尔排序的时间复杂度仍然是 (O(n^2))这使得它在处理大数据集时可能不如其他更高效的排序算法如快速排序、归并排序等。不稳定排序算法希尔排序不是稳定的排序算法相同值的元素可能会因为间隔序列的选择而交换位置。依赖间隔序列希尔排序的性能很大程度上取决于间隔序列的选择选择不当可能会导致性能不如插入排序。
应用场景
小规模数据对于小规模的数据集希尔排序可能比其他算法更快因为其时间复杂度接近线性。简单应用在不需要高精度或稳定性且数据规模不大的情况下希尔排序是一个不错的选择。教育与学习由于其算法实现简单希尔排序常被用于教学帮助初学者理解排序算法的概念。
尽管希尔排序在理论上的时间复杂度不如一些现代排序算法但在实际应用中尤其是在数据量不是非常大时希尔排序由于其低廉的实现成本和较好的性能仍然是一个可行的选择。此外对于一些特定数据结构和数据集通过精心设计的间隔序列希尔排序可以展现出比传统插入排序更好的性能。
时间复杂度
希尔排序的时间复杂度分析相对复杂因为它依赖于间隔序列的选择。以下是几种不同情况下的时间复杂度分析
最坏情况
在最坏的情况下希尔排序的时间复杂度为 (O(n^2))。这是因为在最坏情况下每次插入排序操作都需要移动其他元素。由于希尔排序是通过比较间隔序列中的元素来进行的因此存在一种情况其中间隔序列被设置为非常小的值例如1这实际上将希尔排序转换为普通的插入排序。
平均情况
在平均情况下希尔排序的时间复杂度通常被认为介于 (O(n^{1.3} \log n)) 到 (O(n^{2.25} \log n)) 之间。这是因为在平均情况下插入排序的效率得到了提高因为每次插入操作不需要移动所有的元素。
最佳情况
在最佳情况下希尔排序的时间复杂度可以达到 (O(n \log^2 n))。这是当间隔序列被设计得非常好的情况下例如使用Sedgewick间隔序列时。在这种情况下每次插入操作需要移动的元素数量较少因此整体效率较高。
空间复杂度
希尔排序的空间复杂度为 (O(1))。这是因为希尔排序是原地排序算法除了输入数组本身之外它只需要一个很小的常数空间来存储间隔序列和临时变量。因此希尔排序不需要额外的内存空间来完成排序。
证明
由于希尔排序的时间复杂度分析依赖于间隔序列的选择没有统一的数学证明来确定其时间复杂度。上述的时间复杂度是基于实验和观察得出的而不是精确的数学证明。然而对于特定的间隔序列如Sedgewick间隔序列已经有一些研究表明它在平均和最佳情况下的时间复杂度。 总的来说希尔排序的时间复杂度分析是实验性的而不是理论性的。在实际应用中选择合适的间隔序列可以显著提高希尔排序的性能使其在某些情况下比传统的插入排序更有效率。
代码实现
Python 实现
def shell_sort(arr):n len(arr)gap n // 2while gap 0:for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap // 2C 实现
void shellSort(int arr[], int n) {for (int gap n/2; gap 0; gap / 2) {for (int i gap; i n; i 1) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}C 模板实现
template typename T
void shellSort(vectorT arr)
{// n is the size of the arrayint n arr.size();// gap is the difference between the current position and the gap positionfor (int gap n / 2; gap 0; gap / 2){// i is the current positionfor (int i gap; i n; i){// temp is the current elementT temp arr[i];// j is the gap positionint j;// loop from i to gap and swap the elements if the gap position is greater than the current elementfor (j i; j gap arr[j - gap] temp; j - gap){arr[j] arr[j - gap];}// swap the current element with the gap positionarr[j] temp;}}
}
扩展阅读
优化时间复杂度的思路
选择合适的间隔序列选择一个好的间隔序列是优化希尔排序的关键。Sedgewick间隔序列和Poonen间隔序列是经过精心设计的可以在平均和最佳情况下提供较好的性能。自定义间隔序列根据具体的数据集特点可以设计自定义的间隔序列以适应特定的数据分布从而提高排序效率。减少比较和移动的次数通过改进插入排序的实现减少不必要的比较和元素的移动可以提高希尔排序的效率。
历史上针对希尔排序时间复杂度的变种算法
Sedgewick希尔排序Robert Sedgewick提出了使用特定的间隔序列Sedgewick间隔序列来优化希尔排序。这种方法在平均和最佳情况下提供了较好的性能。Poonen希尔排序Larry Poonen提出了使用一组固定的间隔序列来优化希尔排序这些间隔序列不需要依赖于输入数据的规模。Knuth希尔排序Donald Knuth提出了一种基于斐波那契数列的间隔序列这种方法在某些情况下也表现良好。Hibbard希尔排序虽然不是专门为时间复杂度优化设计的但Hibbard间隔序列在某些情况下也可以提供较好的性能。
除了这些基于间隔序列优化的方法还有一些其他的工作致力于改进希尔排序的性能例如通过减少比较和交换操作来提高效率。然而尽管这些方法可能对特定数据集或特定情况有所帮助但它们并没有产生新的希尔排序变种而是在原有算法基础上的一些改进。希尔排序的时间复杂度优化主要集中在间隔序列的选择和实现细节的优化上。通过选择合适的间隔序列和优化实现可以在一定程度上提高希尔排序的性能。然而需要注意的是希尔排序的时间复杂度仍然在最坏情况下是 (O(n^2))这使得它在处理大数据集时可能不如其他更高效的排序算法。
Hibbard希尔排序
伪代码
function hibbardShellSort(arr):n length(arr)k 1while (2^k - 1) n:k 1for gap 2^(k-1) - 1; gap 0; gap (gap / 2) - 1:for i gap; i n; i:temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempreturn arrPython代码
def hibbard_shell_sort(arr):n len(arr)k 0while (1 k) - 1 n:k 1gaps [1]for i in range(k):gaps.append((1 (2 * i)) - 1)for gap in reversed(gaps):for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempC模板代码
template typename T
void hibbardShellSort(vectorT arr)
{// Calculate the size of the arrayint n arr.size();// Calculate the number of levels in the treeint k 1;// Calculate the number of elements in each level of the treewhile ((1 k) - 1 n){k;}// Sort each level of the treefor (int gap (1 (k - 1)) - 1; gap 0; gap (gap 1) - 1){// Sort each element in the levelfor (int i gap; i n; i){// Store the current element in a temporary variableT temp arr[i];// Find the correct position for the elementint j;for (j i; j gap arr[j - gap] temp; j - gap){// Move the element to the correct positionarr[j] arr[j - gap];}// Put the element in its correct positionarr[j] temp;}}
}完整的项目代码
Python
def shell_sort(arr):n len(arr)gap n // 2while gap 0:for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap // 2def hibbard_shell_sort(arr):n len(arr)k 0while (1 k) - 1 n:k 1gaps [1]for i in range(k):gaps.append((1 (2 * i)) - 1)for gap in reversed(gaps):for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempdef knuth_shell_sort(arr):n len(arr)k 0fib 1while fib n:k 1fib (k % 2 0) and (3 * fib 1) or (3 * fib - 1)gaps [(fib - 1) for i in range(k, 0, -1)]for gap in reversed(gaps):for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempdef sedgewick_shell_sort(arr):n len(arr)gap 1while gap n / 3:gap 3 * gap 1while gap 0:for i in range(gap, n):temp arr[i]j iwhile j gap and arr[j - gap] temp:arr[j] arr[j - gap]j - gaparr[j] tempgap // 3class Person:def __init__(self, name, age, score):self.name nameself.age ageself.score scoredef __lt__(self, other):return self.score other.scoredef __le__(self, other):return self.score other.scoredef __eq__(self, other):return self.score other.score and self.age other.age and self.name other.namedef __ne__(self, other):return not self.__eq__(other)def __gt__(self, other):return self.score other.scoredef __ge__(self, other):return self.score other.scoredef get_name(self):return self.namedef get_age(self):return self.agedef get_score(self):return self.scoredef test_shell_sort():data [9, 8, 3, 7, 5, 6, 4, 1]shell_sort(data)print(data)d_data [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1]shell_sort(d_data)print(d_data)c_data [a, c, b, d, e]shell_sort(c_data)print(c_data)p_data [Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)]shell_sort(p_data)for person in p_data:print(person.get_name(), person.get_age(), person.get_score())def test_hibbard_shell_sort():data [9, 8, 3, 7, 5, 6, 4, 1]hibbard_shell_sort(data)print(data)d_data [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1]hibbard_shell_sort(d_data)print(d_data)c_data [a, c, b, d, e]hibbard_shell_sort(c_data)print(c_data)p_data [Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)]hibbard_shell_sort(p_data)for person in p_data:print(person.get_name(), person.get_age(), person.get_score())def test_knuth_shell_sort():data [9, 8, 3, 7, 5, 6, 4, 1]knuth_shell_sort(data)print(data)d_data [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1]knuth_shell_sort(d_data)print(d_data)c_data [a, c, b, d, e]knuth_shell_sort(c_data)print(c_data)p_data [Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)]knuth_shell_sort(p_data)for person in p_data:print(person.get_name(), person.get_age(), person.get_score())def test_sedgewick_shell_sort():data [9, 8, 3, 7, 5, 6, 4, 1]sedgewick_shell_sort(data)print(data)d_data [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1]sedgewick_shell_sort(d_data)print(d_data)c_data [a, c, b, d, e]sedgewick_shell_sort(c_data)print(c_data)p_data [Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)]sedgewick_shell_sort(p_data)for person in p_data:print(person.get_name(), person.get_age(), person.get_score())if __name__ __main__:test_shell_sort()test_hibbard_shell_sort()test_knuth_shell_sort()test_sedgewick_shell_sort()C
#include iostream
#include array
#include algorithm
#include vector
#include stringusing namespace std;class Person
{
public:Person(string name, int age, int score){this-name name;this-age age;this-socre score;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre of two Person objects.return this-socre other.socre;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator! for other function to use.bool operator!(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre ! other.socre ||this-age ! other.age ||this-name ! other.name;}// Override the operator for other fnction to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Override the operator for other function to use.bool operator(const Person other) const{// Compare the socre, age and name of two Person objects.return this-socre other.socre this-age other.age this-name other.name;}// Now there are some get parameters function for this calss:const string getName() const { return this-name; }int getAge() const { return this-age; }int getScore() const { return this-socre; }private:string name;int age;int socre;
};template typename T
void shellSort(vectorT arr)
{// n is the size of the arrayint n arr.size();// gap is the difference between the current position and the gap positionfor (int gap n / 2; gap 0; gap / 2){// i is the current positionfor (int i gap; i n; i){// temp is the current elementT temp arr[i];// j is the gap positionint j;// loop from i to gap and swap the elements if the gap position is greater than the current elementfor (j i; j gap arr[j - gap] temp; j - gap){arr[j] arr[j - gap];}// swap the current element with the gap positionarr[j] temp;}}
}void shellSortTestCase()
{vectorint data {9, 8, 3, 7, 5, 6, 4, 1};shellSortint(data);for (int i : data){cout i ;}cout endl;vectordouble dData {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};shellSortdouble(dData);for (double i : dData){cout i ;}cout endl;vectorchar cData {a, c, b, d, e};shellSortchar(cData);for (char i : cData){cout i ;}cout endl;vectorPerson pData {Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)};shellSortPerson(pData);for (Person i : pData){cout i.getName() i.getAge() i.getScore() endl;}cout endl;
}template typename T
void hibbardShellSort(vectorT arr)
{// Calculate the size of the arrayint n arr.size();// Calculate the number of levels in the treeint k 1;// Calculate the number of elements in each level of the treewhile ((1 k) - 1 n){k;}// Sort each level of the treefor (int gap (1 (k - 1)) - 1; gap 0; gap (gap 1) - 1){// Sort each element in the levelfor (int i gap; i n; i){// Store the current element in a temporary variableT temp arr[i];// Find the correct position for the elementint j;for (j i; j gap arr[j - gap] temp; j - gap){// Move the element to the correct positionarr[j] arr[j - gap];}// Put the element in its correct positionarr[j] temp;}}
}void hibbardShellSortTestCase()
{vectorint data {9, 8, 3, 7, 5, 6, 4, 1};hibbardShellSortint(data);for (int i : data){cout i ;}cout endl;vectordouble dData {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};hibbardShellSortdouble(dData);for (double i : dData){cout i ;}cout endl;vectorchar cData {a, c, b, d, e};hibbardShellSortchar(cData);for (char i : cData){cout i ;}cout endl;vectorPerson pData {Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)};hibbardShellSortPerson(pData);for (Person i : pData){cout i.getName() i.getAge() i.getScore() endl;}cout endl;
}template typename T
void knuthShellSort(vectorT arr)
{// find the length of the arrayint n arr.size();// initialize the gapint k 0;// initialize the fibonacci numberlong long fib 1;// calculate the fibonacci numberwhile (fib n){k;fib (k % 2 0) ? (3 * fib 1) : (3 * fib - 1);}// create a vector to store the gapsvectorint gaps;// calculate the gapsfor (int i k; i 0; i--){fib (i % 2 0) ? (3 * fib 1) : (3 * fib - 1);gaps.push_back(static_castint(fib) - 1);}// sort the array using the gapsfor (auto gap gaps.rbegin(); gap ! gaps.rend(); gap){// sort the array within the gapfor (int i *gap; i n; i){T temp arr[i];int j;// find the correct positionfor (j i; j *gap arr[j - *gap] temp; j - *gap){arr[j] arr[j - *gap];}arr[j] temp;}}
}void knuthShellSortTestCase()
{vectorint data {9, 8, 3, 7, 5, 6, 4, 1};knuthShellSortint(data);for (int i : data){cout i ;}cout endl;vectordouble dData {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};knuthShellSortdouble(dData);for (double i : dData){cout i ;}cout endl;vectorchar cData {a, c, b, d, e};knuthShellSortchar(cData);for (char i : cData){cout i ;}cout endl;vectorPerson pData {Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)};knuthShellSortPerson(pData);for (Person i : pData){cout i.getName() i.getAge() i.getScore() endl;}cout endl;
}template typename T
void sedgewickShellSort(vectorT arr)
{int n arr.size();int i 0;while ((9 * (1 (2 * i)) - 9 * (1 i) 1) n){i;}vectorint gaps;for (int j 0; j i; j){gaps.push_back(9 * (1 (2 * j)) - 9 * (1 j) 1);}for (auto gap gaps.rbegin(); gap ! gaps.rend(); gap){for (int i *gap; i n; i){T temp arr[i];int j;for (j i; j *gap arr[j - *gap] temp; j - *gap){arr[j] arr[j - *gap];}arr[j] temp;}}
}void sedgewickTestCase()
{vectorint data {9, 8, 3, 7, 5, 6, 4, 1};sedgewickint(data);for (int i : data){cout i ;}cout endl;vectordouble dData {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};sedgewickdouble(dData);for (double i : dData){cout i ;}cout endl;vectorchar cData {a, c, b, d, e};sedgewickchar(cData);for (char i : cData){cout i ;}cout endl;vectorPerson pData {Person(Alice, 20, 90), Person(Bob, 18, 85), Person(Charlie, 22, 95)};sedgewickPerson(pData);for (Person i : pData){cout i.getName() i.getAge() i.getScore() endl;}cout endl;
}int main()
{shellSortTestCase();hibbardShellSortTestCase();knuthShellSortTestCase();sedgewickTestCase();return 0;
}
