數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序

????????????????
????????????????
????????????????????????????????
????????????????????????????????
???? 追風(fēng)趕月莫停留 ????
????????????????????????????????
???? 平蕪盡處是春山????
????????????????????????????????
????????????????????????????????
????????????????
????????????????

??插入排序

??直接插入排序

#include<stdio.h>
/// 直接插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 2; i++)
	{
		int end = i;
		int cur = a[end + 1];
		while (cur >= 0)
		{
			if (cur < a[end])
			{
				a[end + 1] = a[end];
			}
			else
			{
				break;
			}
			end--;
		}
		a[end + 1] = cur;
	}
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	InsertSort(a, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

0到end有序，把end+1序列插入到前序序列
控制[end + 1]序列有序

直接插入排序有點(diǎn)類似尾插，都是從后面開(kāi)始往前比較，和我們平常打撲克洗牌類似。

??希爾排序

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//保證了gap最小為1
		for (int i = 0; i < n - gap; i = i + gap)
		{
			int end = i;
			int cur = a[end + gap];
			while (end >= 0)
			{
				if (cur < a[end])
				{
					a[end + gap] = a[end];
				}
				else
				{
					break;
				}
				end = end - gap;
			}
			a[end + gap] = cur;
		}
	}
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	ShellSort(a, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

該排序就是：預(yù)排序加直接插入排序

gap的作用就是分成多少組，一組一組的排

預(yù)排序的作用就是讓大的數(shù)更快的到后面去，而小的數(shù)更快的到前面來(lái)
在這里gap等于1的時(shí)候就是直接插入排序

??選擇排序

void Swap(int* a1, int* a2)
{
	int cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}
void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = begin;
		int min = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
			if (a[i] > a[max])
			{
				max = i;
			}
		}
		Swap(&a[begin], &a[min]);
		if (max == begin)//特殊情況
		{
			max = min;
		}
		Swap(&a[max], &a[end]);
		begin++;
		end--;
	}
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	SelectSort(a, size);
	Print(a, size);

	return 0;
}

圖里就簡(jiǎn)單列出了三步，幫大家理清程序的邏輯。

選擇排序就是從一堆數(shù)里選出最大和最小，然后最大的放在最右邊，最小的放在最左邊，然后在有效的數(shù)據(jù)長(zhǎng)度里不斷執(zhí)行這一步就可以了。

然而還有一種特殊情況：

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
在圖中，最大的數(shù)恰好是在begin位置上，我們程序上是先把最小的放到最左邊，此時(shí)a[min]和a[begin]就會(huì)互換位置，如下：

此時(shí)max上的數(shù)已經(jīng)不是最大的了，接下來(lái)再把最大的數(shù)放在最右邊，就出錯(cuò)了，所以在這里我們就需要加一個(gè)判斷：

if (max == begin)//特殊情況
		{
			max = min;
		}

大家可能還有疑問(wèn)，我們這里的執(zhí)行順序是先把最小的數(shù)放在最左邊，然后把最大的數(shù)放在最右邊。

有的人肯定就會(huì)問(wèn)如果先執(zhí)行把最大的數(shù)放在最右邊，再執(zhí)行把最小的數(shù)放在最左邊，這樣是不是就不會(huì)出現(xiàn)這種特殊情況了。

但我想說(shuō)的是，如果此時(shí)最小的數(shù)恰好在end上呢，兩種都是特殊的情況，而且類似。

??堆排序

此處排序請(qǐng)看上篇博客：堆和二叉樹(shù)的動(dòng)態(tài)實(shí)現(xiàn)（C語(yǔ)言實(shí)現(xiàn)）,這篇博客詳細(xì)的介紹了堆排序。

??交換排序

??冒泡排序

void Swap(int* a1, int* a2)
{
	int cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}

void BuddleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	BuddleSort(a, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

冒泡排序大家應(yīng)該熟悉，這個(gè)排序就是兩個(gè)兩個(gè)的比較，從第一個(gè)一直比到后面。這個(gè)冒泡排序是最基礎(chǔ)的排序。

??快速排序

??快排（經(jīng)典寫(xiě)法）

void Swap(int* a1, int* a2)
{
	int cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}
int PartSort1(int* a, int left, int right)//單趟
{
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}
		while (left < right && a[left] <= a[key])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[key]);
	return left;
}

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = PartSort1(a, left, right);
	QuickSort1(a, left, key - 1);
	QuickSort1(a, key + 1, right);
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	QuickSort1(a, 0, size - 1);
	Print(a, size);

	return 0;
}

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
上圖中就是單趟的走法。

在單趟走法中有幾個(gè)坑：
（1）第一個(gè)坑就是在第一個(gè)while循環(huán)中有l(wèi)eft<right了有的人就認(rèn)為在while程序內(nèi)部就會(huì)一直維持left<right，其實(shí)是錯(cuò)的。在單趟的走法中，無(wú)論是right往右走，還是left往左走，都有可能left>right發(fā)生。
（2）第二個(gè)坑就是在判斷條件a[key]>=a[right]或者a[key]<=a[left]中，等號(hào)可不可以去掉。在這里可以肯定的是這個(gè)等號(hào)是不可以去掉的，去掉的話會(huì)陷入無(wú)限循環(huán)中。

在這個(gè)排序中，我們還是利用了二叉樹(shù)的知識(shí)點(diǎn)，先從左子樹(shù)排序，然后再是右子樹(shù)，當(dāng)然基礎(chǔ)都是利用了遞歸。

如果有需要了解二叉樹(shù)的知識(shí)可以查看這篇博客：堆和二叉樹(shù)的動(dòng)態(tài)實(shí)現(xiàn)（C語(yǔ)言實(shí)現(xiàn)）,這篇博客詳細(xì)的介紹了堆排序。

??快排（挖坑法）

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int hold = left;
	while (left < right)
	{
		//找小
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hold] = a[right];
		hold = right;
		//找大
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hold] = a[left];
		hold = left;
	}
	a[hold] = key;
	return hold;
}


void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = PartSort2(a, left, right);
	QuickSort2(a, left, key - 1);
	QuickSort2(a, key + 1, right);
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	QuickSort1(a, 0, size - 1);
	Print(a, size);

	return 0;
}

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
快排（挖坑法）這是比較好理解。其中需要注意的和上面的差不多。

??快排（雙指針?lè)ǎ?/h4>

void Swap(int* a1, int* a2)
{
	int cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}
int PartSort3(int* a, int left, int right)
{
	int key = left;
	int cur = left + 1;
	int old = left;
	while (cur <= right)
	{
		if (a[cur] <= a[key])
		{
			old++;
			Swap(&a[old], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[old]);
	return old;
}

void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = PartSort3(a, left, right);
	QuickSort3(a, left, key - 1);
	QuickSort3(a, key + 1, right);
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);
	QuickSort3(a, 0, size - 1);
	Print(a, size);

	return 0;
}

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
這個(gè)雙指針寫(xiě)法，明顯比上面的兩種都好理解，代碼也簡(jiǎn)單些。這個(gè)想法還是如果a[cur]比key大，就光cur++。如果a[cur]比key小，就先old++,再把a(bǔ)[cur]賦給a[old]，然后cur++。整體的思路就是這些。

??快排優(yōu)化

上面我們介紹了三種快排的寫(xiě)法，其中我們?cè)谌ey值的時(shí)候都是取left，left一開(kāi)始都是代表最左邊的數(shù)據(jù)，而在現(xiàn)實(shí)，left代表的值的大小不一定是在中間，如果left代表的值是較小的或者是較大的那么可能對(duì)于快排相較于其它排序來(lái)說(shuō)，此種情況就是快排最壞的情況，可能比堆排或則希爾排序等來(lái)說(shuō)還要慢。

所以在取key值的時(shí)候加了一個(gè)三數(shù)取中的程序：

// 三數(shù)取中
int GetMiddle(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	// left mid right
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])  // mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right]) // mid是最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

這個(gè)程序就是簡(jiǎn)單的取一個(gè)中間數(shù)的大小，這樣快排就不會(huì)出現(xiàn)上面所講的那種情況。

??歸并排序

??歸并排序（遞歸）

void _MergeSort(int* a, int *tem, int left, int right)
{

	//遞歸
	if (right <= left)
		return;
	int mid = (left + right) / 2;
	_MergeSort(a, tem, left, mid);
	_MergeSort(a, tem, mid+1, right);

	//歸并，拷貝到tem中
	int left1 = left, right1 = mid;
	int left2 = mid + 1, right2 = right;
	int sum = left;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] < a[left2])
		{
			tem[sum++] = a[left1++];
		}
		else
		{
			tem[sum++] = a[left2++];
		}
	}

	while (left1 <= right1)
	{
		tem[sum++] = a[left1++];
	}

	while (left2 <= right2)
	{
		tem[sum++] = a[left2++];
	}

	memcpy(a + left, tem + left, (right - left + 1) * sizeof(int));

}

void MergeSort(int* a, int n)
{
	int* tem = (int*)malloc(sizeof(int) * n);
	if (tem == NULL)
	{
		perror("malloc  fail");
		return;
	}

	_MergeSort(a, tem, 0, n - 1);

	free(tem);
}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456 };
	int size = sizeof(a) / sizeof(a[0]);

	MergeSort(a, size);
	Print(a, size);
	return 0;
}

該種排序是利用遞歸實(shí)現(xiàn)的。

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
具體的流程如上面圖中所示。大概就是分為六步，完成后在把數(shù)組拷貝回原來(lái)數(shù)組就可以了

??歸并排序（非遞歸）

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void MergeSortNort(int* a, int n)
{
	int* cur = (int*)malloc(n * sizeof(int));
	if (cur == NULL)
	{
		perror("malloc  fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i = i + 2 * gap)
		{
			int left1 = i, right1 = i + gap - 1;
			int left2 = i + gap, right2 = i + 2 * gap - 1;
			int sum = i;
			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					cur[sum++] = a[left1++];
				}
				else
				{
					cur[sum++] = a[left2++];
				}
			}

			while (left1 <= right1)
			{
				cur[sum++] = a[left1++];
			}
			while (left2 <= right2)
			{
				cur[sum++] = a[left2++];
			}

			memcpy(a + i, cur + i, (2 * gap) * sizeof(int));
		}
		//printf("\n");
		gap = gap * 2;
	}


}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456, };
	int size = sizeof(a) / sizeof(a[0]);
	MergeSortNort(a, size);

	Print(a, size);
	return 0;
}

程序的邏輯就是圖中一步一步的來(lái)，和遞歸的執(zhí)行過(guò)程有些部分是相似的，就是在這里，空間的區(qū)分可能難以讓人理解，大家可以代數(shù)進(jìn)去嘗試，多憑自己的想法寫(xiě)幾遍，大致過(guò)程也就心里有數(shù)了。

大家在圖中也看到了，最后gap取的是偶數(shù)，所以這個(gè)程序的前提條件就是數(shù)據(jù)只能是偶數(shù)次的數(shù)據(jù)，而一旦是奇數(shù)程序就會(huì)報(bào)錯(cuò)。接下來(lái)有一個(gè)修正版，大家可以先把偶數(shù)版的理解了，再去看奇數(shù)版的會(huì)輕松很多。

如果數(shù)據(jù)個(gè)數(shù)是偶數(shù)：
數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序

這里區(qū)間一切正常，也成功排序。

如果數(shù)據(jù)個(gè)數(shù)是奇數(shù)：

從圖中可知，標(biāo)的有箭頭的區(qū)間劃分中，都超出范圍了，所以我們有必要修正

歸并排序優(yōu)化：

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void MergeSortNort(int* a, int n)
{
	int* cur = (int*)malloc(n * sizeof(int));
	if (cur == NULL)
	{
		perror("malloc  fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i = i + 2 * gap)
		{
			int left1 = i, right1 = i + gap - 1;
			int left2 = i + gap, right2 = i + 2 * gap - 1;
			printf("[%d  %d]  [%d  %d]\n", left1, right1, left2, right2);
			//如果第二組不存在，這一組就不用歸并
			if (left2 >= n)
			{
				break;
			}
			//如果第二組右邊見(jiàn)越界了，就修正一下
			if (right2 >= n)
			{
				right2 = n - 1;
			}

			int sum = i;
			while (left1 <= right1 && left2 <= right2)
			{
				if (a[left1] < a[left2])
				{
					cur[sum++] = a[left1++];
				}
				else
				{
					cur[sum++] = a[left2++];
				}
			}

			while (left1 <= right1)
			{
				cur[sum++] = a[left1++];
			}
			while (left2 <= right2)
			{
				cur[sum++] = a[left2++];
			}

			memcpy(a + i, cur + i, (right2 - i + 1) * sizeof(int));
		}
		gap = gap * 2;
	}


}

int main()
{
	int a[] = { 2,66,34,5,123,34,345,456, 3};
	int size = sizeof(a) / sizeof(a[0]);
	MergeSortNort(a, size);

	Print(a, size);
	return 0;
}

修正后的程序，主要增加了2個(gè)判斷和修改了范圍。

兩個(gè)判斷：數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序
第一個(gè)判斷是防止第二組區(qū)間不存在，就直接結(jié)束，如：

當(dāng)然有的人就會(huì)問(wèn)，在這個(gè)圖中第一個(gè)區(qū)間的right2不是也超了嗎，為什么不要判斷right1呢？

大家可以試著想一想，如果right2超過(guò)了區(qū)間范圍，left2是不是有可能也超過(guò)了范圍。而left2超出范圍了,right1是不是一定超出了范圍。這就是一個(gè)誰(shuí)先誰(shuí)后的問(wèn)題。大家可以仔細(xì)想一想，可以代數(shù)進(jìn)去嘗試一下。而且你判斷了left2超出區(qū)間了，程序就已經(jīng)跳出循環(huán)了。

第二個(gè)判斷：

就是right2超出了區(qū)間范圍，而left2沒(méi)有超出，只需要把right2修正到有效范圍就可以了，如上圖所示，只需要把15修正成8，就可以了。

今天排序的知識(shí)點(diǎn)就得差不多了，本人水平有限，可以知識(shí)點(diǎn)尚未完全覆蓋，請(qǐng)大家多多指教，謝謝！?。。。。?！

數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）,數(shù)據(jù)結(jié)構(gòu)與算法,c語(yǔ)言,排序算法,開(kāi)發(fā)語(yǔ)言,數(shù)據(jù)結(jié)構(gòu),算法,排序文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844822.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法——排序（C語(yǔ)言實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！