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

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的烏爾禾網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

  對(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ū)過程，將比這個(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ù)。可是，這很難算出來，并且會(huì)明顯減慢快速排序的速度。這樣的中值的估計(jì)可以通過隨機(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 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);
			}
		}
	}
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

當(dāng)前標(biāo)題：快速排序的幾種優(yōu)化-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/csghdi.html