本文將介紹三種排序算法--插入排序，希爾排序，堆排序。本文所有例子都是使用升序

我們提供的服務有：做網(wǎng)站、成都網(wǎng)站設計、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、巍山ssl等。為1000多家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術(shù)的巍山網(wǎng)站制作公司

  一.插入排序

   算法思想

    維護一個有序數(shù)組，將要插入的數(shù)據(jù)與有序數(shù)組自最后一個元素直到合適位置的數(shù)一一比較。

eg: 有序數(shù)組：1，3，5，6，7   現(xiàn)在待插入數(shù)據(jù)為2，那么他將會和7，6，5，3，依次作比較，當帶插入數(shù)據(jù)小于有序數(shù)組最后的元素大小，則將該元素后移，直到待插入元素找到合適位置為止。

   代碼實現(xiàn)

void InsertSort(int* a, int size)
{
	assert(a);
	for (int i = 0; i < size - 1; ++i)
	{
		int end = i;                                 //標識有序數(shù)組的最后一位
		int tmp = a[end + 1];
		while (end >= 0 && tmp < a[end])
		{
			a[end + 1] = a[end];                     //待插入數(shù)據(jù)比有序數(shù)組的最后一個數(shù)小，將有序數(shù)組最后一位向后移位
			--end;
		}
		a[end + 1] = tmp;
	}
}

   總結(jié)

    1.插入排序可以認為是間距為1的插入算法，說這個是為了待會兒更好的理解希爾排序。

    2.插入排序的時間復雜度為O(n^2);

    3.插入排序的空間復雜度為O(1);

    4.具有穩(wěn)定性

 排序算法的穩(wěn)定性是指，經(jīng)過排序算法排序的相同元素的相對位置不會發(fā)生改變。

  二.希爾排序

   算法思想

    希爾排序可以認為是插入排序的增強版，因為，他加入了一個預排的過程，即在實現(xiàn)間距為1的插入算法之前，他已經(jīng)預先將間距為gap（gap一直減減直到>0）的數(shù)組排列過了。所以，當進行g(shù)ap = 1的插入排序之前使得待排序數(shù)組已經(jīng)高度接近有序，使得這次進行的gap = 1的排序的時間復雜度，可以小于O(N^2)(gap = 1的插入排序，最好情況的時間復雜度為O(1)，前面的預排過程正是出于這個目的)。

   代碼實現(xiàn)

//希爾排序
void ShellSort(int* a,size_t size)
{
	assert(a);
	int gap = size / 2;
	while (gap > 0)
	{
		for (int i = 0; i < size - gap; ++i)
		{
			int end = i;                                
			int tmp = a[end + gap];
			while (end >= 0 && tmp < a[end])
			{
				a[end + gap] = a[end];                    
				end -= gap;
			}
			a[end + gap] = tmp;
		}
		--gap;
	}
}

  總結(jié)

 上圖為gap = 5 的時候的預排效果圖

 1.希爾排序預排的思想和插入排序的思想是一致的，只是，他把原數(shù)組分成不同的區(qū)間。

 2.希爾排序的時間復雜度為O(N^2),空間復雜度為O(1);

 3，具有不穩(wěn)定性

 三.堆排序

  算法思想

代碼實現(xiàn)

void AdjustDown(int* a, size_t size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child= 0; --i)  //從第一個非葉子節(jié)點開始調(diào)
	{
		AdjustDown(a, size, i);
	}
	for (size_t i = 0; i < size; ++i)
	{
		swap(a[0], a[size - 1 - i]);
		AdjustDown(a, size - i - 1, 0);
	}
}

 總結(jié)

 1.時間復雜度為O(N*lgN),空間復雜度為O(1);

 2.具有不穩(wěn)定性

 以上就是本人在學習過程中的一些經(jīng)驗總結(jié)。當然，本人能力有限，難免會有紕漏，希望大家可以指正。