希爾排序是在直接插入排序的基礎上的一種優化：因為在逆序情況下，直接插入排序每次插入都要比較大小，遍歷一邊陣列元素，復雜度很高；
所以針對這種情況，偉大的希爾，提出了將陣列每輪元素間隔一定距離，重新分組插入排序，gap越大，逆序情況下，大資料就越快回到陣列高位，gap=1時，就是直接插入
#include<stdio.h>
/*專案需求：對一個陣列中的元素進行，插入排序
插入排序：插入一個數字，按照大小順序在整個陣列中排序；類似于接牌的程序，
按照牌的大小給牌排序，同時牌越來越多，占用的空間也是越來越大*/
//直接插入排序
int* InserSort(int* arr, int sz);
//希爾排序
int* ShellSort(int* arr, int sz,int gap);
//列印
void Print(int* arr);
void main() {
//定義一個陣列
int arr[10] = {7,5,3,1,2,4,9,6,8,0};
int sz = sizeof(arr) / sizeof(int);
//Print(arr);
//printf("\n");
//Print(InserSort(arr, sz));
int gap1 = 3;
Print(ShellSort(arr,sz,gap1));
printf("\n");
//int gap2 = 3;
//Print(ShellSort(arr, sz, gap2));
//printf("\n");
/*int gap3 = 1;
Print(ShellSort(arr, sz, gap3));
printf("\n");*/
}
//升序
int* InserSort(int* arr, int sz) {
int end = 0;
int tem = 0;
for (size_t i = 0; i < sz-2; i++)
{
end = i;
tem = arr[end + 1];
while (end>=0) {
if (arr[end] > tem) {
arr[end + 1] = arr[end];
end--;
}
else {
break;
}
}
//這里是兩種情況：1.break出來，插入隊中；2.回圈結束出來，插入隊頭；
arr[end + 1] = tem;
}
return arr;
}
void Print(int* arr) {
for (size_t j = 0; j < 10; j++)
{
printf("%d ", arr[j]);
}
}
int* ShellSort(int* arr, int sz , int gap) {
/*gap > 1 時，都是預排序
gap = 1 時，是插入排序*/
while (gap>1)
{
gap = gap / 2;
for (size_t i = 0; i < sz - gap; i++)
{
int end = i;
//end +gap的后一位元素
int tem = arr[end + gap];
while (end >= 0) {
if (arr[end] > tem) {
arr[end + gap] = arr[end];
end = end - gap;
}
else {
break;
}
}
//這里是兩種情況：1.break出來，插入隊中；2.回圈結束出來，插入隊頭；
arr[end + gap] = tem;
}
}
return arr;
}
結果為：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294659.html
標籤：其他
上一篇：Spark的RDD行動算子