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

   排序是面試?？嫉牡念}，對于快速排序是對冒泡排序的一種改進(jìn)。

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

//1、快速排序一般

//排序思想：

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

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

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

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

//引入的原因：

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

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

//事實(shí)上，隨機(jī)性并沒有多大的幫助，因此一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數(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ù)列中取出一個數(shù)作為基準(zhǔn)數(shù)key

//2.設(shè)計(jì)兩個指針，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è)計(jì)思想：

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

//2、先壓小再壓大

//3、判斷棧是否為空

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

//5、直到棧為空

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