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

   排序是面試常考的的題，對于快速排序是對冒泡排序的一種改進。

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

//1、快速排序一般

//排序思想：

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

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

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

    
int PartSort(int* a, int left, int right)
{
    int key = a[right];//找最右邊一個為基準
    int begin = left;
     int end = right - 1;
  while (begin < end)
  {
       while (begin < end&&a[begin] <= key)//當找到大于基準數(shù)時停
        {
           ++begin;
         }
      while (begin < end&&a[end] >= key)//當找到小于基準數(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ù)列中取出一個數(shù)作為基準數(shù)。

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

//3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(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ù)取中

//引入的原因：

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

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

//事實上，隨機性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數(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è)計思想：

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

//2.設(shè)計兩個指針，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++;
		}
	}//此時next==end跳出循環(huán)
	QuickSort3(a, left, cur - 1);
	QuickSort3(a, end + 1, right);
}

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

//設(shè)計思想：

//1、先進行部分排序分成兩部分

//2、先壓小再壓大

//3、判斷棧是否為空

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

//5、直到棧為空

int PartSort4(int* a, int left, int right)
{
	int key = a[right];//找最右邊一個為基準
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		while (begin < end&&a[begin] <= key)//當找到大于基準數(shù)時停
		{
			++begin;
		}
		while (begin < end&&a[end] >= key)//當找到小于基準數(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);
			}
		}
	}
}

 

 

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

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

廣告

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