排序-插入排序与希尔排序

一、插入排序

思路：

当插入第i(i>=1)个元素时，前面的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 怎么设置呢？，我们知道，当gap=1时就是相当于直接插入排序，因此我们可以这样设置，就是gap 由大到小，最后到1，结束
4.gap设置的特点
gap越大，大的数可以越快排到后面，小的数可以越快的排到前面，但是预排完，不是那么接近有序
gap越小 越接近有序
gap=1，就是直接插入排序
如：

代码实现：

void test1(int arr[], int size) {
	int gap = size;//设为数据的个数
	int ned = 0;
	while (gap!= 1)//结束条件；当gap=1时
	{
		gap = gap / 3 + 1;//除三或者二都可，每次都会减少，加1保证有一次gap=1
		//每间隔gap的数据就进行一次插入排序
		//结束条件：当i+gap>n时
		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;
				}
				else
					break;

			}
			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)
当然这只时估算的结果，不一定准确
严蔚敏老师他的数据结构这本书上是：O（N^1.3）

以上就是我的分享了，如果有什么错误，欢迎在评论区留言。
最后，谢谢大家的观看！