希爾排序算法的C說話完成示例。本站提示廣大學習愛好者:(希爾排序算法的C說話完成示例)文章只能為提供參考,不一定能成為您想要的結果。以下是希爾排序算法的C說話完成示例正文
希爾排序,也稱遞加增量排序算法,是拔出排序的一種更高效的改良版本。希爾排序長短穩固排序算法。
希爾排序是基於拔出排序的以下兩點性質而提出改良辦法的:
拔出排序在對簡直曾經排好序的數據操作時,效力高,便可以到達線性排序的效力
但拔出排序普通來講是低效的,由於拔出排序每次只能將數據挪動一名
希爾排序經由過程將比擬的全體元素分為幾個區域來晉升拔出排序的機能。如許可讓一個元素可以一次性地朝終究地位進步一年夜步。然後算法再取愈來愈小的步出息行排序,算法的最初一步就是通俗的拔出排序,然則到了這步,需排序的數據簡直是已排好的了(此時拔出排序較快)。
假定有一個很小的數據在一個已按升序排好序的數組的末尾。假如用龐雜度為O(n2)的排序(冒泡排序或拔出排序),能夠會停止n次的比擬和交流能力將該數據移至准確地位。而希爾排序會用較年夜的步長挪動數據,所以小數據只需停止多數比擬和交流便可到准確地位。
一個更好懂得的希爾排序完成:將數組列在一個表中並對列排序(用拔出排序)。反復這進程,不外每次用更長的列來停止。最初全部表就只要一列了。將數組轉換至表是為了更好地輿解這算法,算法自己僅僅對原數組停止排序(經由過程增長索引的步長,例如是用i += step_size而不是i++)。
C說話完成示例
#include<stdio.h> #include<stdlib.h> #include<time.h> #define LEN 10 typedef int dataType; //初始化數組,賦值整數隨機數 void initArr(dataType arr[], int len); //希爾排序 void shellSort(dataType arr[], int len); //交流兩個數 void swap(dataType &x,dataType &y); //打印數組元素 void print(dataType arr[], int len); int main() { dataType arr[LEN]; initArr(arr,LEN); printf("================希爾排序================"); //輸入排序前的數組元素 printf("\n排序前數組元素:"); print(arr,LEN); shellSort(arr,LEN); printf("\n排序後數組元素:"); print(arr,LEN); printf("\n"); return 0; } //初始化數組,賦值整數隨機數 void initArr(dataType arr[], int len) { int i = 0; srand((unsigned)time(NULL)); for(i = 0; i < len; i++) arr[i] = rand(); } //希爾排序 void shellSort(dataType arr[], int len) { int h = 0; int i = 0; int j = 0; //設置步長 for(h = 1; h < len; h = 3 * h + 1) ; while(h) { h /= 3; if(h < 1) break; for(i = h; i < len; i++) for(j = i; j >= h; j-=h) { if(arr[j-h] < arr[j]) break; swap(arr[j-h],arr[j]); } } } //交流兩個數 void swap(dataType &x,dataType &y) { dataType temp; temp = x; x = y; y = temp; } //打印數組元素 void print(dataType arr[], int len) { int i = 0; for(i = 0; i< LEN; i++) { if(i % 5 == 0) { printf("\n"); } printf("%d\t",arr[i]); } }