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

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

非遞歸算法——快速排序、歸并排序

2年前作者：保護(hù)小周?分類：Toy博客閱讀(20)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了非遞歸算法——快速排序、歸并排序。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

非遞歸算法——快速排序、歸并排序

哈嘍大家好，我是保護(hù)小周?，本期為大家?guī)淼氖浅Ｒ娕判蛩惴ㄖ械?strong>快速排序、歸并排序，非遞歸算法，分享所有源代碼，粘貼即可運(yùn)行，保姆級(jí)講述，包您一看就會(huì)，快來試試吧~

非遞歸算法——快速排序、歸并排序

目錄

一、遞歸的缺陷

1.1 棧是什么，數(shù)據(jù)結(jié)構(gòu)“?！庇质鞘裁?，他們之間有什么區(qū)別？

1.2 C/C++ 程序內(nèi)存分配的幾個(gè)區(qū)域：

二、快排非遞歸算法

2.1 算法思想

2.2 程序?qū)崿F(xiàn)

?QuickSort.c

三、歸并非遞歸算法

3.1 算法思想

3.2?程序?qū)崿F(xiàn)

3.3?拓展知識(shí)

四、總結(jié)

五、棧（Stack）源代碼

Stack.h

Stack.c

一、遞歸的缺陷

遞歸的缺陷：如果棧幀深度太深（遞歸的次數(shù)多），棧空間不夠用（大概只有幾兆）可能會(huì)溢出。

一般校招可能考察的就是非遞歸算法，知道你會(huì)遞歸算法，偏偏考你非遞歸，您能咋辦吶，多學(xué)點(diǎn)唄，運(yùn)籌帷幄，方能立于不敗之地。

遞歸改非遞歸的方法：

  1. 直接改循環(huán)（簡單一點(diǎn)的遞歸）
  2. 借助數(shù)據(jù)結(jié)構(gòu)的“?！蹦M遞歸過程（復(fù)雜一點(diǎn)的遞歸）

1.1 棧是什么，數(shù)據(jù)結(jié)構(gòu)“?！庇质鞘裁?，他們之間有什么區(qū)別？

非遞歸算法——快速排序、歸并排序

非遞歸算法——快速排序、歸并排序

函數(shù)調(diào)用建立棧幀，棧幀中存儲(chǔ)局部變量，參數(shù)等等。

棧區(qū)，堆區(qū)等是操作系統(tǒng)這門學(xué)科中對(duì)內(nèi)存的劃分，數(shù)據(jù)結(jié)構(gòu)的“?！保岸选笔谴娣?、處理數(shù)據(jù)的一種結(jié)構(gòu)，跟內(nèi)存的棧區(qū)，堆區(qū)，沒有啥關(guān)系，但是有一點(diǎn)，數(shù)據(jù)結(jié)構(gòu)的“?！焙蛢?nèi)存的棧區(qū)都是后進(jìn)先出。

1.2 C/C++ 程序內(nèi)存分配的幾個(gè)區(qū)域：

1.棧區(qū)（stack）:在執(zhí)行函數(shù)時(shí)，函數(shù)內(nèi)局部變量的存儲(chǔ)單元都可以在棧上創(chuàng)建，函數(shù)執(zhí)行結(jié)束時(shí)這些存儲(chǔ)單元自動(dòng)釋放。棧內(nèi)存分配運(yùn)算內(nèi)置于處理器的指令集中，效率很高，但是分配的內(nèi)存容量有限，棧區(qū)主要存放運(yùn)行函數(shù)而分配的局部變量，函數(shù)參數(shù)，返回?cái)?shù)據(jù)，返回地址等。

2.堆區(qū)（heap）：一般由程序員分配釋放，若程序員不釋放，程序結(jié)束時(shí)由OS回收。

3.數(shù)據(jù)段（靜態(tài)區(qū)）（static）存放全局變量，靜態(tài)變量。程序結(jié)束后由系統(tǒng)釋放。

4.代碼段：存放函數(shù)體（類成員函數(shù)和全局函數(shù)）的二進(jìn)制代碼

二、快排非遞歸算法

快速排序(Quicksort)是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換排序方法，有時(shí)候也叫做劃分交換排序，是一個(gè)高效的算法，其基本思想為：任取待排序 元素序列中的某元素作為基準(zhǔn)值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有 元素均小于基準(zhǔn)值，右子序列中所有元素均大于基準(zhǔn)值，然后最左右子序列重復(fù)該過程，直到所 有元素都排列在相應(yīng)位置上為止。這是一個(gè)分治算法，而且它就在原地交換數(shù)據(jù)排序。

如果大家對(duì)快速排序的邏輯，遞歸算法還不熟悉的朋友可以觀看博主的另一篇博客，快排遞歸算法分享了三種方法：挖坑法，左右指針法，前后指針法，以及兩種優(yōu)化方式：解決快排最壞情況的“三數(shù)取中”，避免遞歸次數(shù)過多的"小區(qū)間優(yōu)化"。

常見排序算法之交換排序——冒泡排序、快速排序_保護(hù)小周?的博客-CSDN博客

2.1 算法思想

借助數(shù)據(jù)結(jié)構(gòu)的“?！蹦M遞歸過程，原理其實(shí)跟遞歸差不多，只是不是由操作系統(tǒng)自己建立棧幀，同時(shí)堆區(qū)上的空間是夠的。我們分割的區(qū)間其實(shí)是由數(shù)據(jù)結(jié)構(gòu)“?！睅臀覀儽４嫫饋砹耍鰲^(qū)間，循環(huán)執(zhí)行單趟排，這就是模擬遞歸的原理。

非遞歸算法——快速排序、歸并排序

?用一組數(shù)據(jù)，簡單的讓大家了解了一下，模擬遞歸是個(gè)咋回事。

2.2 程序?qū)崿F(xiàn)

首先咱們要寫個(gè)棧，不要慌，博主稍后會(huì)在后面附上棧的完整代碼，沒辦法，誰叫C語言沒有自己的庫嘞，C++,Java,庫里都有棧。

以博主使用的編譯器為例：啟動(dòng)　Visual　Studio　2019，創(chuàng)建新項(xiàng)目——＞空項(xiàng)目——＞創(chuàng)建項(xiàng)目名稱，選擇保存地址，然后我們打開解決方案資源管理器，找到源文件，添加以下三個(gè)文件（文件名不定，關(guān)于棧的程序博主已經(jīng)寫好了）。

Stack.h ——關(guān)于程序相關(guān)函數(shù)的聲明，符號(hào)聲明，頭文件包含等（棧）

Stack.c—— 程序相關(guān)函數(shù)的實(shí)現(xiàn)(棧)

QuickSort.c ——程序的邏輯（非遞歸快排）

非遞歸算法——快速排序、歸并排序

?QuickSort.c

#include"Stack.h"http://引用一手我們自己寫的頭文件，不要用<>,這個(gè)是引用庫里的

//挖坑法單趟排
int QuickSort(int* a, int left, int right)//升序
{
	int begin = left;
	int end = right;
	int pivot = begin;//記錄坑位的下標(biāo)
	int key = a[begin];//坑值

	while (begin < end)
	{
		//右邊找小，放到左邊
		while (begin < end && a[end] >= key)//與坑值比較
		{
			--end;
		}
		//小的放在左邊的坑里，自己形成了新的坑位
		a[pivot] = a[end];
		pivot = end;

		//左邊找大，放在右邊
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		//大的放在右邊的坑里，自己形成了新的坑位
		a[pivot] = a[begin];
		pivot = begin;
	}
	a[pivot] = key;
	return pivot;//返回坑位
}

//借助數(shù)據(jù)結(jié)構(gòu)棧模擬遞歸過程
void QuickSortNonR(int *a,int n)
{
	Stack com;//定義Stack結(jié)構(gòu)體類型變量
	STDataTYpe scope;//這個(gè)結(jié)構(gòu)體類型的變量主要存儲(chǔ)數(shù)據(jù)區(qū)間[left,right]。
	
	//初始化棧
	StackInit(&com);

	scope.left =0;
	scope.right= n - 1;
	//入棧(區(qū)間)
	StackPush(&com,scope);

	while (!StackEmpty(&com))//判斷棧是否為空
	{
		//記錄一下左右區(qū)間，不然區(qū)間結(jié)構(gòu)的值會(huì)因?yàn)檩敵鰲ｍ斣囟淖?		int left = scope.left;
		int right = scope.right;
		
		scope = StackTop(&com);//輸出棧頂元素
		StackPop(&com);//出棧

		//挖坑法單趟排
		int keyIndex = QuickSort(a, scope.left, scope.right);
		
		//分割區(qū)間
		//[left,keyIndex-1], keyIndex ,[keyIndex+1,right]
		//區(qū)間只有一個(gè)元素或區(qū)間不存在，不執(zhí)行入棧scope
		//注意入棧順序
		if (keyIndex + 1 < right)//區(qū)間只有一個(gè)元素或區(qū)間不存在，不執(zhí)行入棧
		{
			scope.left = keyIndex + 1;
			scope.right = right; 
			
			StackPush(&com, scope);//入棧
		}

		if (left < keyIndex-1)//后進(jìn)先出
		{
			scope.left = left;
			scope.right = keyIndex - 1;

			StackPush(&com, scope);//入棧
		}
	}
	//釋放空間
	StackDesTory(&com);//在堆區(qū)上開辟的空間，用完之后需要主動(dòng)free釋放。
}

//打印
void Print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	int a[] = {49,38,65,97,76,13,27,49};
	//挖坑法
	QuickSortNonR(a,sizeof(a) / sizeof(a[0]));
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

非遞歸算法——快速排序、歸并排序

三、歸并非遞歸算法

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法 （Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序 列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

如果大家對(duì)歸并排序的邏輯，遞歸的遞歸算法還不了解的朋友可以觀看博主的另一篇博客。

常見排序算法之歸并排序——?dú)w并排序_保護(hù)小周?的博客-CSDN博客

3.1 算法思想

本次不使用棧模擬遞歸，而是用循環(huán)代替遞歸，首先通過循環(huán)控制gap來劃分區(qū)間，然后子循環(huán)遍歷每一個(gè)區(qū)間，每一個(gè)區(qū)間，執(zhí)行歸并操作（升序取?。?，主要難點(diǎn)是控制區(qū)間越界問題。

? gap：每組數(shù)據(jù)個(gè)數(shù)，n為數(shù)組長度

（1）歸并過程中右半?yún)^(qū)間可能不存在（程序會(huì)劃分左右區(qū)間，右半?yún)^(qū)間的值>n-1越界），因?yàn)樵乜赡懿皇?的次方倍。

? ? ? ? ?解決方法，break;中止循環(huán)，就不會(huì)執(zhí)行歸并操作，一個(gè)區(qū)間是不用歸并的。

（2）歸并過程中右半?yún)^(qū)間的值<gap（最后一個(gè)區(qū)間<gap），也會(huì)造成越界訪問。

? ? ? ? 解決方法，重新劃分邊界值，避免越界，區(qū)間右值=n-1（n為數(shù)組長度）;然后遍歷區(qū)間執(zhí)行歸并就不會(huì)越界了。

非遞歸算法——快速排序、歸并排序

3.2?程序?qū)崿F(xiàn)

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>//動(dòng)態(tài)開辟空間的函數(shù)的頭文件

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

//歸并非遞歸排序
void MergeSortNonR(int *a,int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//動(dòng)態(tài)開辟與待排序數(shù)組大小相等的一片連續(xù)的空間

	//gap=1是區(qū)間[0,0],[1,1],[2,2]……歸并
	//gap=2是區(qū)間[0,1],[2,3],[4,5]……歸并
	//gap=4是區(qū)間[0,3],[4,7],[8,11]……歸并
	//……
	int gap = 1;//每組數(shù)據(jù)個(gè)數(shù)
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)//可以轉(zhuǎn)到下一對(duì)區(qū)間
		{
			//[i,i+gap-1] ,[i+gap,i+2*gap-1]……
			//歸并
			int begin1 = i, end1 = i+gap-1;
			int begin2 = i+gap, end2 = i + 2 * gap - 1;

			//歸并過程中右半?yún)^(qū)間可能不存在，因?yàn)榭赡懿皇?的整數(shù)倍
			if (begin2 >n-1)
				break;//中止程序

			//歸并過程中右半?yún)^(qū)間的值<gap，也會(huì)造成越界訪問
			if (end2 >n-1)
				end2 = n - 1;//重新劃分邊界值，避免越界

			int index = i;

			while (begin1 <= end1 && begin2 <= end2)//有一個(gè)子序列遍歷完，循環(huán)結(jié)束
			{
				if (a[begin1] < a[begin2])//升序，取小
				{
					tmp[index++] = a[begin1++];

				}
				else
				{
					tmp[index++] = a[begin2++];
				}
			}

			//判斷子序列是否遍歷完，未遍歷完畢的子序列剩余元素直接給到tmp數(shù)組
			while (begin1 <= end1)
			{
				tmp[index++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[index++] = a[begin2++];
			}
			//拷貝回去
			for (int j = i; j <= end2; ++j)
			{
				a[j] = tmp[j];
			}
		}
		gap *= 2;
	}
	free(tmp);//釋放動(dòng)態(tài)開辟的空間
}
int main()
{
	int a[] = {10,6,7,1,3,9,4,2};
	MergeSortNonR(a, sizeof(a) / sizeof(a[0]));
	//MergeSort(a,sizeof(a)/sizeof(a[0]));
	Print(a,sizeof(a)/sizeof(a[0]));
	return 0;
}

非遞歸算法——快速排序、歸并排序

3.3?拓展知識(shí)

歸并排序也叫外排序，可以對(duì)文件中數(shù)據(jù)進(jìn)行排，假設(shè)10G的數(shù)據(jù)放到硬盤的文件中，要排序，如何排，如果操作系統(tǒng)將這組數(shù)據(jù)調(diào)入內(nèi)存中，可能內(nèi)存不夠。其他的排序自然而然就用不了，假設(shè)有1G的內(nèi)存可用。10G的文件切分為10個(gè)1G的文件，并且讓10個(gè)1G的文件有序。每次讀一個(gè)1G的文件到內(nèi)存，放到一個(gè)數(shù)組，用快排對(duì)其排序，再將有序數(shù)據(jù)寫回文件，再繼續(xù)讀下一個(gè)文件。得到10個(gè)有序的1G文件，即可用遞歸排序，兩兩一組，合成一個(gè)新的有序文件。

關(guān)于文件的讀寫操作，感興趣的同學(xué)可以訂閱博主的專欄C語言，里面有文件的基本操作（上）（下），同時(shí)C技能樹，文件的基本操作也收錄了這兩篇博客。

C語言_保護(hù)小周?的博客-CSDN博客

四、總結(jié)

非遞歸算法與遞歸算法相比起來性能上來將其實(shí)并沒有很大的提升，遞歸對(duì)于現(xiàn)在的CPU性能來講也是沒有問題的，主要是怕極端情況下，就數(shù)據(jù)量特別多的時(shí)候，需要建立很深的棧幀，?？臻g不夠，如果使用數(shù)據(jù)結(jié)構(gòu)的“?！蹦M遞歸，就不會(huì)出現(xiàn)這種情況（數(shù)據(jù)結(jié)構(gòu)棧是在內(nèi)存的堆區(qū)上建立的，而堆是用G做單位）。

至此快速排序、歸并排序的非遞歸算法博主已經(jīng)分享完了，相信大家對(duì)這個(gè)邏輯有了一定的理解，大家可以自己動(dòng)手敲敲代碼，感受一下。

非遞歸算法——快速排序、歸并排序

?本期收錄于博主的專欄——排序算法，適用于編程初學(xué)者，感興趣的朋友們可以訂閱，查看其它“常見排序”。排序算法_保護(hù)小周?的博客-CSDN博客

感謝每一個(gè)觀看本篇文章的朋友，更多精彩敬請(qǐng)期待：保護(hù)小周???*★,°*:.☆(￣▽￣)/$:*.°★*??

文章多處存在借鑒，如有侵權(quán)請(qǐng)聯(lián)系修改刪除！非遞歸算法——快速排序、歸并排序?文章來源地址http://www.zghlxwxcb.cn/news/detail-402183.html

五、棧（Stack）源代碼

Stack.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//數(shù)據(jù)類型
typedef struct STDataTYpe//區(qū)間
{
	int left;
	int right;
}STDataTYpe;//方便以后更改類型


//棧的定義
typedef struct Stack
{
	STDataTYpe* data;
	int top;//棧頂，記錄有多少數(shù)據(jù)
	int capacity;//記錄動(dòng)態(tài)數(shù)組的最大空間，增容
}Stack;


//初始化
void StackInit(Stack*ps);

//入棧
void StackPush(Stack*ps,STDataTYpe x);

//出棧
void StackPop(Stack*ps);

//輸出棧頂
STDataTYpe StackTop(Stack*ps);

//輸出棧數(shù)據(jù)個(gè)數(shù)
int  StackSize(Stack *ps);

//判斷棧是否為空
bool StackEmpty(Stack* ps);

//釋放空間
void StackDesTory(Stack* ps);

Stack.c

#include"Stack.h"

//初始化
void StackInit(Stack* ps)
{
	ps->data = (STDataTYpe*)malloc(sizeof(STDataTYpe)*4);
	if (ps->data== NULL)//判斷是否申請(qǐng)成功
	{
		perror("malloc");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
	//區(qū)間初始化
	ps->data->left = 0;
	ps->data->right = 0;
}

//入棧
void StackPush(Stack* ps, STDataTYpe scope)
{
	assert(ps);
	//滿了擴(kuò)容
	if (ps->top==ps->capacity)
	{
		STDataTYpe* tmp = (STDataTYpe*)realloc(ps->data, ps->capacity * 2*sizeof(STDataTYpe));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		else
		{
			ps->data = tmp;
			ps->capacity *= 2;
		}
	}
	//區(qū)間入棧
	ps->data[ps->top].right = scope.right;
	ps->data[ps->top].left = scope.left;

	ps->top++;
}

//出棧
void StackPop(Stack* ps)
{
	assert(ps);
	//?？眨{(diào)用Pop,直接中止元素
	assert(ps->top>=0);
	ps->top--;
}

//輸出棧頂
STDataTYpe StackTop(Stack* ps)
{
	assert(ps);
	//?？眨{(diào)用Top,直接中止元素
	assert(ps->top >= 0);
	return ps->data[ps->top-1];
}

//輸出棧數(shù)據(jù)個(gè)數(shù)
int StackSize(Stack *ps)
{
	assert(ps);
	return ps->top;
}

//判斷棧是否為空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

//釋放空間
void StackDesTory(Stack* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = ps->capacity = 0;
}

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

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

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

相關(guān)文章

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

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

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

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包