一：插入排序

/** 插入排序在哪些情況下效率高？* 1.插入的序列基本有序* 2.序列較小的情況下*/#include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h>#define MAX 10//獲取時(shí)間，毫秒 long getTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm; }//打印 void PrintArr(int* arr, int len) {for (int i = 0; i < len; i++){printf("%d ", arr[i]);} }//插入排序 void Insert_Sort(int* arr,int len) {for (int i = 1; i < len;i++)//第一個(gè)數(shù)作為有序序列{if (arr[i - 1]>arr[i]){int j;int temp = arr[i];for (j = i - 1; j >= 0 && (arr[j] > temp);j--)//第一輪各個(gè)數(shù)不斷跟temp比{//如2 4 8 0arr[j + 1] = arr[j];}//循環(huán)完以后[] 2 4 8; temp=0 j在-1位arr[j + 1] = temp;}} }int main(void) {int arr[MAX];srand((unsigned int)time(NULL));for (int i = 0; i < MAX; i++){arr[i] = rand() % MAX;}printf("插入排序前：");PrintArr(arr, MAX);long t_start = getTime();Insert_Sort(arr, MAX);long t_end = getTime();printf("\n");printf("插入排序后：");PrintArr(arr, MAX);printf("\n");printf("插入排序共花費(fèi)%ld毫秒\n", t_end - t_start); }

二：希爾排序

/* * 插入排序在哪些情況下效率高？ * 1.插入的序列基本有序 * 2.序列較小的情況下 */#include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h>#define MAX 10//獲取時(shí)間，毫秒 long getTime() {struct timeb tb;ftime(&tb);return tb.time * 1000 + tb.millitm; }//打印 void PrintArr(int* arr, int len) {for (int i = 0; i < len; i++){printf("%d ", arr[i]);} }//希爾排序 void Shell_Sort(int arr[],int len) {int increment = len;int i, j, k;while (increment>1)//increment此處不能等于1，//increment = 2 / 3 + 1=1；increment=1就只有一個(gè)組，下面循環(huán)一次就可以了，假如=1，就會(huì)無(wú)限循環(huán){increment = increment / 3 + 1;//每次的步長(zhǎng)，如原始increment也就是len=4，現(xiàn)在increment=2//現(xiàn)在increment=2,就相當(dāng)于將數(shù)據(jù)分為2個(gè)組，increment是多少組也就是多少for (i = 0; i < increment;i++){//i相當(dāng)于共有多少個(gè)組//總數(shù)據(jù)：2 1 0 3 4 5 6 7 8 9//如第一組：2 0 4 6 8；i=0//如第二組：1 3 5 7 9for (j = i + increment; j < len;j+=increment)//從第一組第二個(gè)開(kāi)始，0開(kāi)始，j+步長(zhǎng)=4{if (arr[j - increment]>arr[j])//2>0{//把0緩存下來(lái) 2 ' '4 6 8int temp = arr[j];//temp(0)依次和前面比較，空格' '放在比temp小的后面for (k = j - increment; (k >= 0) && (arr[k] > temp);k-=increment){//arr[k]=2,k指向2,空格' '往前移動(dòng)//' ' 2 4 6 8arr[k + increment] = arr[k];}//循環(huán)完以后，k=k-increment;如k此處就在-1//將temp放入空格' ':0 2 4 6 8arr[k + increment] = temp;}}}} }int main(void) {int arr[MAX];srand((unsigned int)time(NULL));for (int i = 0; i < MAX; i++){arr[i] = rand() % MAX;}printf("希爾排序前：");PrintArr(arr, MAX);long t_start = getTime();Shell_Sort(arr, MAX);long t_end = getTime();printf("\n");printf("希爾排序后：");PrintArr(arr, MAX);printf("\n");printf("希爾排序共花費(fèi)%ld毫秒\n", t_end - t_start); }

總結(jié)

以上是生活随笔為你收集整理的数据结构二：排序（插入排序和希尔排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。