創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),青原企業(yè)網(wǎng)站建設(shè),青原品牌網(wǎng)站建設(shè),網(wǎng)站定制,青原網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,青原網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

   排序是面試常考的的題，對(duì)于快速排序是對(duì)冒泡排序的一種改進(jìn)。

   對(duì)于快排：我在這寫了幾種實(shí)現(xiàn)方法：

//1、快速排序一般

//排序思想：

//1.從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot），

//2.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

//3.遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

    
int PartSort(int* a, int left, int right)
{
    int key = a[right];//找最右邊一個(gè)為基準(zhǔn)
    int begin = left;
     int end = right - 1;
  while (begin < end)
  {
       while (begin < end&&a[begin] <= key)//當(dāng)找到大于基準(zhǔn)數(shù)時(shí)停
        {
           ++begin;
         }
      while (begin < end&&a[end] >= key)//當(dāng)找到小于基準(zhǔn)數(shù)時(shí)停
     {
      --end;
     }
     if (begin < end)
       {
          swap(a[begin], a[end]);
        }
   }
    if (a[begin]>a[right])
   {
      swap(a[begin], a[right]);
      return begin;
    }
    else
    {
    return right;
     }
}
void QuickSort(int* a, int left, int right)
{
    assert(a);
     if (left >= right)
      return;
    int div = PartSort(a, left, right);//快排挖坑法
    QuickSort(a, left, div - 1);
    QuickSort(a, div + 1, right);
}

//2、挖坑法

//該方法的基本思想是：

//1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。

//2．分區(qū)過(guò)程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。

//3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。

int PartSort1(int *a, int left, int right)
{
	assert(a);
	int key = a[right];
	while (left < right)
	{
		while (left < right && a[left] <= key)//從左向右找比key大的值
			left++;
		if (left < right)
		{
			a[right] = a[left];
			right--;
		}
		while (left < right && a[right] > key)//從右向左找比key小的值
			right--;
		if (left < right)
		{
			a[left] = a[right];
			left++;
		}
	}
	a[left] = key;
	return left;
}
void QuickSort1(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
	int div = PartSort1(a, left, right);//快排挖坑法
	QuickSort1(a, left, div - 1);
	QuickSort1(a, div + 1, right);
}

//3、三數(shù)取中

//引入的原因：

//雖然隨機(jī)選取樞軸時(shí)，減少出現(xiàn)不好分割的幾率，但是還是最壞情況下還是O(n ^ 2），要緩解這種情況，就引入了三數(shù)取中選取樞軸

//分析：最佳的劃分是將待排序的序列分成等長(zhǎng)的子序列，最佳的狀態(tài)我們可以使用序列的中間的值，也就是第N / 2個(gè)數(shù)。可是，這很難算出來(lái)，并且會(huì)明顯減慢快速排序的速度。這樣的中值的估計(jì)可以通過(guò)隨機(jī)選取三個(gè)元素并用它們的中值作為樞紐元而得到。

//事實(shí)上，隨機(jī)性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個(gè)元素的中值作為樞紐元。顯然使用三數(shù)中值分割法消除了預(yù)排序輸入的不好情形，并且減少快排大約14%的比較次數(shù)

int Midfind(int *a, int left, int right)
{
	int mid = left - (left - right) / 2;
	if (a[left] >= a[right])
	{
		if (a[right] > a[mid])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else  if (a[left] < a[mid])
	{
		return mid;
	}
	else
	{
		return left;
	}
}

void QuickSort2(int* a, int left, int right)//三數(shù)取中
{
	assert(a);
	if (left > right)
		return;
	int mid = Midfind(a, left, right);
	swap(a[mid], a[right]);
	int div = PartSort(a, left, right);
	QuickSort2(a, left, div - 1);
	QuickSort2(a, div + 1, right);
}

//4、單向

//設(shè)計(jì)思想：

//1.先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)key

//2.設(shè)計(jì)兩個(gè)指針，cur，prev，cur開始指向首元素，next開始指向（即cur后一位）。

//3.若next大于key就與往最后交換  end左移

//4.若next小于key就交換cur。next

//5.等于key next就往后移

void  QuickSort3(int *a, int left, int right)//單向（排序）
{
	assert(a);
	if (left > right)
	{
		return;
	}
	int key = a[left];
	int cur = left;
	int next = left + 1;
	int end = right;
	while (next <= end)
	{
		if (a[next] > key)
		{
			swap(a[next], a[end]);
			end--;
		}
		else if (a[next] < key)
		{

			swap(a[cur], a[next]);  //一直交換 ，待cur左邊都小于key，右邊都大于key為止。
			cur++;
			next++;
		}
		else
		{
			next++;
		}
	}//此時(shí)next==end跳出循環(huán)
	QuickSort3(a, left, cur - 1);
	QuickSort3(a, end + 1, right);
}

//5、非遞歸形式(借助棧)

//設(shè)計(jì)思想：

//1、先進(jìn)行部分排序分成兩部分

//2、先壓小再壓大

//3、判斷棧是否為空

//4、不為空，取棧頂（就是先取出一部分重復(fù)步驟2）；

//5、直到棧為空

int PartSort4(int* a, int left, int right)
{
	int key = a[right];//找最右邊一個(gè)為基準(zhǔn)
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		while (begin < end&&a[begin] <= key)//當(dāng)找到大于基準(zhǔn)數(shù)時(shí)停
		{
			++begin;
		}
		while (begin < end&&a[end] >= key)//當(dāng)找到小于基準(zhǔn)數(shù)時(shí)停
		{
			--end;
		}
		if (begin < end)
		{
			swap(a[begin], a[end]);
		}
	}
	if (a[begin]>a[right])
	{
		swap(a[begin], a[right]);
		return begin;
	}
	else
	{
		return right;
	}
}
void QuickSort4(int *a, int left, int right)
{
	
	stack<int> ch;
	if (left < right)
	{
		int mid = PartSort4(a, left, right);
		if (left < mid - 1)
		{
			ch.push(left);
			ch.push(mid - 1);
		}
		if (mid + 1 < right)
		{
			ch.push(mid + 1);
			ch.push(right);
		}
		while (!ch.empty())
		{
			int tmp = ch.top();
			ch.pop();
			int cur = ch.top();
			ch.pop();
			int mid = PartSort(a, cur, tmp);
			if (cur < mid - 1)
			{
				ch.push(cur);
				ch.push(mid - 1);
			}
			if (mid + 1 < tmp)
			{
				ch.push(mid + 1);
				ch.push(tmp);
			}
		}
	}
}

 

 

標(biāo)題名稱：快速排序的幾種優(yōu)化
文章網(wǎng)址：http://chinadenli.net/article46/jgjshg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站制作、響應(yīng)式網(wǎng)站、面包屑導(dǎo)航、ChatGPT、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)