国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

2年前作者：Hayaizo分類：Toy博客閱讀(25)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

1.排序的概念及其運(yùn)用

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。

外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

1.2排序運(yùn)用
1.3 常見的排序算法
// 排序?qū)崿F(xiàn)的接口

// 插入排序
void InsertSort(int* a, int n);

// 希爾排序
void ShellSort(int* a, int n);

// 選擇排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n)

// 快速排序遞歸實(shí)現(xiàn)
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指針法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);

// 快速排序 非遞歸實(shí)現(xiàn)
void QuickSortNonR(int* a, int left, int right)

// 歸并排序遞歸實(shí)現(xiàn)
void MergeSort(int* a, int n)
// 歸并排序非遞歸實(shí)現(xiàn)
void MergeSortNonR(int* a, int n)

// 計(jì)數(shù)排序
void CountSort(int* a, int n)

// 測試排序的性能對比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int)*N);
	int* a2 = (int*)malloc(sizeof(int)*N);
	int* a3 = (int*)malloc(sizeof(int)*N);
	int* a4 = (int*)malloc(sizeof(int)*N);
	int* a5 = (int*)malloc(sizeof(int)*N);
	int* a6 = (int*)malloc(sizeof(int)*N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];

	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N-1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);

	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

######排序OJ(可使用各種排序跑這個(gè)OJ)OJ鏈接

2.常見排序算法的實(shí)現(xiàn)
2.1 插入排序
2.1.1基本思想：

直接插入排序是一種簡單的插入排序法，其基本思想是：

把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。

實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想

2.1.2直接插入排序：

當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移

直接插入排序的特性總結(jié)：

  1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
  2. 時(shí)間復(fù)雜度：O(N^2)
  3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
  4. 穩(wěn)定性：穩(wěn)定
//插入排序
void InsertSort(int* a, int length)
{
	for (int i = 1; i < length; i++)
	{
		int end = i - 1;
		int num = a[i];
		while (end >= 0)
		{
			if (num < a[end])
			{
				a[end + 1] = a[end];//挪動數(shù)組
				end--;
			}
			else
			{
				break;//找到了要插入的點(diǎn)
			}
		}
		a[end + 1] = num;
	}
}
2.1.3 希爾排序( 縮小增量排序 )

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

//希爾排序
void ShellSort(int* a, int length)
{
	//接近有序
	int gap = length;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < length - gap; i++)
		{
			int end = i;
			int num = a[i + gap];
			while (end >= 0)
			{
				if (a[end] > num)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = num;
		}
	}
}

希爾排序的特性總結(jié)：

  1. 希爾排序是對直接插入排序的優(yōu)化。

  2. 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測試的對比。

  3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定：

《數(shù)據(jù)結(jié)構(gòu)(C語言版)》— 嚴(yán)蔚敏

《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》— 殷人昆

因?yàn)檎兊膅ap是按照Knuth提出的方式取值的，而且Knuth進(jìn)行了大量的試驗(yàn)統(tǒng)計(jì)，我們暫時(shí)就按照： O ( n 1.25 ) O(n^{1.25}) O(n1.25) 到 O ( 1.6 ? n 1.25 ) O(1.6*n^{1.25}) O(1.6?n1.25)來算。

  1. 穩(wěn)定性：不穩(wěn)定
2.2 選擇排序

2.2.1基本思想：

每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完 。

2.2.2 直接選擇排序:

  • 在元素集合array[i]–array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素

  • 若它不是這組元素中的最后一個(gè)(第一個(gè))元素，則將它與這組元素中的最后一個(gè)（第一個(gè)）元素交換

  • 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重復(fù)上述步驟，直到集合剩余1個(gè)元素

//選擇排序
void SelectSort(int* a, int length)
{
	int left = 0, right = length - 1;
	while (left < right)
	{
		int maxi = left, mini = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[left], &a[mini]);
		if (left == maxi) maxi = mini;
		Swap(&a[right], &a[maxi]);
		left++;
		right--;
	}
}
直接選擇排序的特性總結(jié)：
  1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
  2. 時(shí)間復(fù)雜度：O(N^2)
  3. 空間復(fù)雜度：O(1)
  4. 穩(wěn)定性：不穩(wěn)定
2.2.3 堆排序

堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，它是選擇排序的一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆，排降序建小堆。

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

//堆排序
void AdjustDown(int* a, int sz, int parent)
{
	//調(diào)大堆
	assert(a);
	int child = parent * 2 + 1;
	while (child < sz)//兒子節(jié)點(diǎn)要存在
	{
		//找左右兒子中最大的那個(gè)
		if (child + 1 < sz && a[child] < a[child + 1])
		{
			child++;//找到了最大的那個(gè)
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void SetHeap(int* a, int sz)
{
	assert(a);
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, sz, i);
	}
}

void heap_sort(int* a, int sz)
{
	int num = sz;
	SetHeap(a, sz);
	while (num)
	{
		Swap(&a[0], &a[num-1]);
		num--;
		AdjustDown(a, num, 0);
	}
}
直接選擇排序的特性總結(jié)：
  1. 堆排序使用堆來選數(shù)，效率就高了很多。
  2. 時(shí)間復(fù)雜度：O(N*logN)
  3. 空間復(fù)雜度：O(1)
  4. 穩(wěn)定性：不穩(wěn)定
2.3 交換排序

基本思想：所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來對換這兩個(gè)記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

2.3.1冒泡排序
//冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		bool exchange = false;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				exchange = true;
			}
		}
		if (exchange == false)
		{
			break;
		}
	}
}

冒泡排序的特性總結(jié)：

  1. 冒泡排序是一種非常容易理解的排序
  2. 時(shí)間復(fù)雜度：O(N^2)
  3. 空間復(fù)雜度：O(1)
  4. 穩(wěn)定性：穩(wěn)定
2.3.2 快速排序

快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

// 假設(shè)按照升序?qū)rray數(shù)組中[left, right)區(qū)間中的元素進(jìn)行排序
void QuickSort(int array[], int left, int right)
{
  if(right - left <= 1)
      return;

  // 按照基準(zhǔn)值對array數(shù)組的 [left, right)區(qū)間中的元素進(jìn)行劃分
  int div = partion(array, left, right);

  // 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)
  // 遞歸排[left, div)
  QuickSort(array, left, div);

  // 遞歸排[div+1, right)
  QuickSort(array, div+1, right);
}

上述為快速排序遞歸實(shí)現(xiàn)的主框架，發(fā)現(xiàn)與二叉樹前序遍歷規(guī)則非常像，同學(xué)們在寫遞歸框架時(shí)可想想二叉樹前序遍歷規(guī)則即可快速寫出來，后序只需分析如何按照基準(zhǔn)值來對區(qū)間中數(shù)據(jù)進(jìn)行劃分的方式即可。

將區(qū)間按照基準(zhǔn)值劃分為左右兩半部分的常見方式有：

  1. hoare版本
//hoare版本
void QuickSort(int* a, int left,int right)
{
	if (left >= right) return;
	
	int begin = left, end = right;
	int keyi = left;
	int mid = GetMid(a, left, right);
	Swap(&a[left], &a[mid]);
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}

		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = right;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
  1. 挖坑法
//挖坑法
void QuickSort(int* a, int left, int right)
{
	if (left >= right) return;
	
	int key = a[left];
	int begin = left, end=right;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[left] = a[right];
		
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[right] = a[left];
	}
	a[left] = key;
	int keyi = left;
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}
  1. 前后指針版本
//前后指針快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	
	int cur = left + 1, prev = left;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur > prev)
		{
			prev++;
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	int mid = prev;
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid+1, right);
}

2.3.2 快速排序優(yōu)化

  1. 三數(shù)取中法選key
int GetMid(int* a,int left,int right)
{
	int mid = left + right >> 1;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else//a[left]>a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[mid])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
  1. 遞歸到小的子區(qū)間時(shí)，可以考慮使用插入排序
//小區(qū)間優(yōu)化
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if ((right - left + 1) > 10)
	{
		int cur = left + 1, prev = left;
		int keyi = left;
		while (cur <= right)
		{
			if (a[cur] < a[keyi] && cur > prev)
			{
				prev++;
				Swap(&a[cur], &a[prev]);
			}
			cur++;
		}
		Swap(&a[prev], &a[keyi]);
		int mid = prev;
		QuickSort(a, left, mid - 1);
		QuickSort(a, mid + 1, right);
	}
	else
	{
		InsertSort(a + left, right - left + 1);
	}
}
2.3.2 快速排序非遞歸
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, left);
	StackPush(&st, right);

	while (StackEmpty(&st) != 0)
	{
		right = StackTop(&st);
		StackPop(&st);
		left = StackTop(&st);
		StackPop(&st);

      if(right - left <= 1)
          continue;

		int div = PartSort1(a, left, right);
       // 以基準(zhǔn)值為分割點(diǎn)，形成左右兩部分：[left, div) 和 [div+1, right)
      StackPush(&st, div+1);
	    StackPush(&st, right);

		StackPush(&st, left);
		StackPush(&st, div);
	}

  StackDestroy(&s);
}

int OnceSort(int* a, int left, int right)
{
	if (left > right)
	{
		return;
	}
	int key = a[left];
	while (left < right)
	{
		//先算右邊，右邊找大
		while (left<right&&a[right] >= key)
		{
			right--;
		}
		//找到了就交換
		a[left] = a[right];
		while (left<right&&a[left] <= key)
		{
			left++;
		}
		a[right] = a[left];
	}
	a[left] = key;//將key放在正確的位置上
	int meeti = left;//相遇的點(diǎn)
	return meeti;
}

void QuickSort(int* a, int left, int right)
{
	ST st;//創(chuàng)建一個(gè)棧來模擬遞歸的過程
	STInit(&st);
	STPush(&st,right);
	STPush(&st,left);
	while (!STEmpty(&st))
	{
		//左區(qū)間
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);
		int mid = OnceSort(a, begin, end);
       
		if(end > mid + 1)
		{
			STPush(&st, end);
			STPush(&st, mid + 1);
		}
       //如果left>=mid-1說明左邊已經(jīng)排完序了
       if(begin < mid - 1)
		{
			STPush(&st,mid - 1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

在這里判斷if語句的條件為什么不取=號呢？

假如我們?nèi)×说扔谔枺?/p>

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

會出現(xiàn)很多沒必要的判斷，begin和end相等的時(shí)候就是只有一個(gè)元素，一個(gè)元素是不需要排序的，所以不用取=號

如果沒有取=號的話：

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

快速排序的特性總結(jié)：

  1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序

  2. 時(shí)間復(fù)雜度：O(N*logN)

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

  1. 空間復(fù)雜度：O(logN)

  2. 穩(wěn)定性：不穩(wěn)定

2.4 歸并排序

基本思想：

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
歸并排序核心步驟：[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-svQBGJGJ-1683775858015)(C:/Users/19735/Desktop/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%88%9D%E9%98%B6V5-2021%E4%BF%AE%E8%AE%A2/Lesson6–%E6%8E%92%E5%BA%8F/12.jpg)]

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

//歸并排序遞歸
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}
	
	int mid = begin + end >> 1;
	_MergeSort(a, begin, mid,tmp);
	_MergeSort(a, mid+1, end,tmp);
	
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	
	//處理剩余的
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int sz)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	_MergeSort(a, 0, sz - 1, tmp);
	
	free(tmp);
}

//歸并排序非遞歸
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	int gap = 1;//分組，組間距
	while (gap < n)
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int j = i;
			if (begin1>=n||end1 >= n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}
			printf("[%d %d] [%d %d]\n", begin1, end1, begin2, end2);
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		gap *= 2;
	}
	free(tmp);
}

如果不對區(qū)間進(jìn)行修正：

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

可以看到原數(shù)組本來只有9個(gè)元素，有效區(qū)間是[0,8]但上述運(yùn)行中明顯有超過這個(gè)區(qū)間的區(qū)間，那這是什么原因?qū)е碌哪兀?/p>

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

框框中的代碼當(dāng)gap很大的時(shí)候就會產(chǎn)生越界，但由于begin2依舊滿足小于end2所以程序會繼續(xù)進(jìn)行

代碼運(yùn)行過程：

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

歸并排序的特性總結(jié)：
  1. 歸并的缺點(diǎn)在于需要O(N)的空間復(fù)雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
  2. 時(shí)間復(fù)雜度：O(N*logN)
  3. 空間復(fù)雜度：O(N)
  4. 穩(wěn)定性：穩(wěn)定
2.5 非比較排序

思想：計(jì)數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。
操作步驟：

  1. 統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
  2. 根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列中快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解 
//計(jì)數(shù)排序
void CountSort(int* a, int n)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < n; ++i)
	{
		if (a[i] > max)
		{
			max = a[i];
		}

		if (a[i] < min)
		{
			min = a[i];
		}
	}

	int range = max - min + 1;
	int* countA = (int*)malloc(sizeof(int) * range);
	if (countA == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	memset(countA, 0, sizeof(int) * range);

	// 計(jì)數(shù)
	for (int i = 0; i < n; i++)
	{
		countA[a[i] - min]++;
	}

	// 排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (countA[i]--)
		{
			a[j++] = i + min;
		}
	}

	free(countA);
}
計(jì)數(shù)排序的特性總結(jié)：
  1. 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是適用范圍及場景有限。
  2. 時(shí)間復(fù)雜度：O(MAX(N,范圍))
  3. 空間復(fù)雜度：O(范圍)
  4. 穩(wěn)定性：穩(wěn)定
3.排序算法復(fù)雜度及穩(wěn)定性分析

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解

快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解文章來源地址http://www.zghlxwxcb.cn/news/detail-437959.html

4.選擇題練習(xí)
1. 快速排序算法是基于（    ）的一個(gè)排序算法。
A 分治法
B 貪心法
C 遞歸法
D 動態(tài)規(guī)劃法

2.對記錄（54,38,96,23,15,72,60,45,83）進(jìn)行從小到大的直接插入排序時(shí)，當(dāng)把第8個(gè)記錄45插入到有序表時(shí)，為找到插入位置需比較（ ）次？（采用從后往前比較）
A 3
B 4
C 5
D 6

3.以下排序方式中占用O（n）輔助存儲空間的是
A 選擇排序
B 快速排序
C 堆排序
D 歸并排序

4.下列排序算法中穩(wěn)定且時(shí)間復(fù)雜度為O(n2)的是（ ）
A 快速排序
B 冒泡排序
C 直接選擇排序
D 歸并排序

5.關(guān)于排序，下面說法不正確的是
A 快排時(shí)間復(fù)雜度為O(N*logN)，空間復(fù)雜度為O(logN)
B 歸并排序是一種穩(wěn)定的排序,堆排序和快排均不穩(wěn)定
C 序列基本有序時(shí)，快排退化成冒泡排序，直接插入排序最快
D 歸并排序空間復(fù)雜度為O(N), 堆排序空間復(fù)雜度的為O(logN)

6.下列排序法中，最壞情況下時(shí)間復(fù)雜度最小的是（ ）
A 堆排序
B 快速排序
C 希爾排序
D 冒泡排序

7.設(shè)一組初始記錄關(guān)鍵字序列為(65,56,72,99,86,25,34,66)，則以第一個(gè)關(guān)鍵字65為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）
A 34，56，25，65，86，99，72，66
B 25，34，56，65，99，86，72，66
C 34，56，25，65，66，99，86，72
D 34，56，25，65，99，86，72，66

答案：
1.A
2.C
3.D
4.B
5.D
6.A
7.A

到了這里，關(guān)于快速排序、希爾排序、歸并排序、堆排序、插入排序、冒泡排序、選擇排序(遞歸、非遞歸)C語言詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包