常见的网站布局结构,房地产开发建设网站,宁远做网站,佛山做优化的网络公司文章目录 一、插入排序二、希尔排序 一、插入排序
思路#xff1a; 当插入第i(i1)个元素时#xff0c;前面的array[0],array[1],…,array[i-1]已经排好序#xff0c;此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较#xff0c;找到插入位置即将… 文章目录 一、插入排序二、希尔排序 一、插入排序
思路 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 如 代码实现
void test(int arr[],int size) {int ned ;//定义一个插入数据的前一个数据的下标for (int i 0; i size-1; i) {ned i;//从第一个开始int t arr[ned 1];//需要插入的数据while (ned 0)//当遍历到最后一个结束{if (arr[ned] t)//比插入数据大就插入{arr[ned 1] arr[ned];//往后移动一位ned--;//--找下一个数据}else//找到比t小的结束break;}arr[ned 1] t;//在比t小的数据前一位插入
//这样就算那个数是最小的我和下标为0那个位置比完后ned-1
//我们也可以插入到下标为0 的位置}
}
void Print(int arr[], int size) {for (int i 0; i size; i)printf(%d , arr[i]);printf(\n);
}
int main() {int arr[] { 8,6,9,3,5,1,0,4,2,7 };Print(arr, sizeof(arr) / sizeof(arr[0]));test(arr, sizeof(arr)/sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));return 0}
运行结果 时间复杂度 第一层循环怎么都要走N次第二层循环最好的结果为已经排好序为1次 最坏的结果与想要的顺序相反为N次 我们取最坏的结果N ^ N次所以时间复杂度O(N^N).
二、希尔排序
思路 1.实质上还是使用插入排序的思想 2.我们将数组的数据进行分组排序每间隔 gap 的为一组这些排序叫做预排序设置多组间隔为 gap 经过预排序的数组就会接近有序 如
3.那么这个 gap 怎么设置呢我们知道当gap1时就是相当于直接插入排序因此我们可以这样设置就是gap 由大到小最后到1结束 4.gap设置的特点 gap越大大的数可以越快排到后面小的数可以越快的排到前面但是预排完不是那么接近有序 gap越小 越接近有序 gap1就是直接插入排序 如
代码实现
void test1(int arr[], int size) {int gap size;//设为数据的个数int ned 0;while (gap! 1)//结束条件当gap1时{gap gap / 3 1;//除三或者二都可每次都会减少加1保证有一次gap1//每间隔gap的数据就进行一次插入排序//结束条件当igapn时for (int i 0; i size - gap; i){//以下和我们上面的插入排序一样ned i;int t arr[ned f];while (ned 0) {if (arr[ned] t) {arr[ned gap] arr[ned];ned - gap;}elsebreak;}arr[ned gap] t;}}
}
void Print(int arr[], int size) {for (int i 0; i size; i)printf(%d , arr[i]);printf(\n);
}int main() {int arr[] { 8,6,9,3,5,1,0,4,2,7 };Print(arr, sizeof(arr) / sizeof(arr[0]));test1(arr, sizeof(arr) / sizeof(arr[0]));Print(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}运行结果 时间复杂度 第一次循环每次除3就是以3为底的logN 当gap很大时因为循环的次数减少所以后两层循环的次数很接近N 当gap很小时因为已经接近有序了所以循环的次数也接近N 所以时间复杂度为 O(lonN*N)(以3为底的logN) 当然这只时估算的结果不一定准确 严蔚敏老师他的数据结构这本书上是ON^1.3
以上就是我的分享了如果有什么错误欢迎在评论区留言。 最后谢谢大家的观看
