插入排序，希爾排序，堆排序

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

  一.插入排序

   算法思想

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

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

   代碼實(shí)現(xiàn)

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

   總結(jié)

    1.插入排序可以認(rèn)為是間距為1的插入算法，說(shuō)這個(gè)是為了待會(huì)兒更好的理解希爾排序。

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

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

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

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

  二.希爾排序

   算法思想

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

   代碼實(shí)現(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 的時(shí)候的預(yù)排效果圖

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

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

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

 三.堆排序

  算法思想

代碼實(shí)現(xiàn)

void AdjustDown(int* a, size_t size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child<size)
	{
		if (child+1<size && a[child] < a[child + 1])
			++child;
		if (a[parent] < a[child])
		{
			swap(a[parent], a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
		
	}
}
void HeapSort(int* a,size_t size)
{
	assert(a);
	//建堆
	for (int i = (size - 2) / 2; i >= 0; --i)  //從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(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.時(shí)間復(fù)雜度為O(N*lgN),空間復(fù)雜度為O(1);

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

 以上就是本人在學(xué)習(xí)過(guò)程中的一些經(jīng)驗(yàn)總結(jié)。當(dāng)然，本人能力有限，難免會(huì)有紕漏，希望大家可以指正。