#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

//直接排序：指的是設(shè)定2個(gè)下標(biāo)/指針。然后從下標(biāo)1開始進(jìn)行比較，
//升序情況下：若在前的下標(biāo)/指針大于當(dāng)前比較數(shù)值。就進(jìn)行數(shù)組的后移。
//直到滿足當(dāng)前序列值。然后最終將當(dāng)前比較數(shù)值進(jìn)行替換。
//PS：總有一個(gè)指針遍歷比較數(shù)組（k，arry[i]）
//時(shí)間復(fù)雜度為：0（n^2）,空間復(fù)雜度0（1）
void InsertSort(int* arry,int len)
{
	assert(arry);
	for(int i = 1; i < len;++i)
	{
		int j = i-1;
		int k = arry[i];
		while(j > -1 && arry[j] > k)
		{
			arry[j + 1] = arry[j];
			--j;
		}
		arry[j+1] = k;
	}
}

//希爾排序：在直接排序的基礎(chǔ)上增加分組Gap值，
//利用Gap值，比較對(duì)應(yīng)（len/gap）* i的位置。每個(gè)位置代表一個(gè)分組
//然后將i的值依次增加到len-gap的位置相當(dāng)于我已經(jīng)比較了每個(gè)對(duì)應(yīng)分組，使當(dāng)前序列趨近于有序。
//然后我們縮小gap值的范圍，使其接近于2，證明還需要進(jìn)行分組排序。
//0(n^2),0(1);
void ShellSort(int *arry,int len)
{
	assert(arry);
	int gap = len;
	while(gap > 1)
	{
		gap = gap/3 + 1;
		for(int i = 0; i < len - gap;++i)
		{
			int j = i;
			int k = arry[i+gap];
			while(j > -1 && arry[j] > k)
			{
				arry[j + gap] = arry[j];
				j -= gap;
			}
			arry[j+gap] = k;
		}
	}
}

//選擇排序：其實(shí)這個(gè)排序的思路比較簡單，我們只需要每次遍歷數(shù)組
//得到最小/最大（或者2者都選），然后將最大值最小值分別丟到數(shù)組的最左端還有最右端然后縮小范圍就可以了。
//然后值得注意的是。我們?cè)谕瑫r(shí)得出當(dāng)前最大最小值時(shí)候，需要注意
//當(dāng)前選出的最大值最小值在進(jìn)行其中一次交換后，會(huì)不會(huì)將max與min相交換。
//0（n^2）,0(1)

void SelectSort(int *arry, int len)
{
	assert(arry);
	for(int i = 0, j = len-1;i < j;++i,--j)
	{
		int min = i;
		int max = j;
		for(int k = i;k <= j;++k)
		{
			if(arry[k] < arry[min])
			{
				min = k;
			}
			if(arry[k] > arry[max])
			{
				max = k;
			}

			if(min != i)
			{
				int temp = arry[min];
				arry[min] = arry[i];
				arry[i] = temp;
			
				if(max == i)
					max = min;
			}

			if(max!= j)
			{
				int temp = arry[max];
				arry[max] = arry[j];
				arry[j] = temp;
			}
		}
	}
}

//冒泡排序：冒泡排序比較簡單，就不多說了。
//需要注意的是我們可以利用一個(gè)標(biāo)記值來確定我們需不需要進(jìn)行這一次的冒泡
//如果需要進(jìn)行冒泡的話我們的標(biāo)記值就會(huì)設(shè)置位開關(guān)。
//然后我們就可以減少我們所需要排序的次數(shù)。
//0(n^2),0(1)

void BubbleSort(int *arry,int len)
{
	assert(arry);
	for(int i = 0;i < len -1;++i)
	{
		for(int j = len - 1;j >= i;--j)
		{
			if(arry[j] < arry[j-1])
			{
				int temp = arry[j];
				arry[j] = arry[j - 1];
				arry[j - 1] = temp;
			}
		}
	}
}


//快速排序：我們快速排序的大概思路就是選擇一頭一尾的2個(gè)下標(biāo)/指針,然后我們利用指針選擇法
//將大數(shù)與小數(shù)集中排列。將我們所選的key值建為關(guān)鍵值，大于放左邊，小于放右邊。然后不斷縮小范圍就好了
//提高效率的辦法就是我們可以在當(dāng)前序列的值小于某個(gè)數(shù)值的時(shí)候我們選擇使用插入排序。
//這可以有效的提高我們排序的效率。
//一前一后只適用于數(shù)組。
//0（nlogn）,0(logn)
int _QuickSort(int* arry,int left,int right)
{
	assert(arry);
	if(left >= right)
		return  0;
	int tmp = arry[right];
	int index = right;
	--right;
	while(left <right)
	{
		while(left < right && arry[left] <= tmp)
			++left;
		while(left < right && arry[right] >= tmp)
			++right;
		if(left < right)
		{
			swap(arry[left],arry[right]);
		}
	}
	if(tmp <= arry[right])
	{
		swap(arry[right],arry[index]);
	}
	return right;
}

void QuickSort(int *arry,int left,int right)
{
	assert(arry);
	if(left < right)
	{
		int mid = _QuickSort(arry,left,right);
		QuickSort(arry,mid+1,right);
		QuickSort(arry,left,mid-1);

	}
}


//快速排序：前后指針，我們選擇一個(gè)緊緊跟隨的2個(gè)指針，原理跟一前一后相同，知識(shí)進(jìn)行了大數(shù)小數(shù)的堆置、
//這樣的方法可以利用到指針中，當(dāng)然了，key值得選擇很重要，
//最壞的情況就是選擇到了有序數(shù)組的最大數(shù)/最小數(shù)，就會(huì)出現(xiàn)最壞的情況。
//選擇3數(shù)取中法可以有效地避免這個(gè)情況的出現(xiàn)。


void swap(int* arry,int left,int right)
{
	int tmp;
	tmp = arry[left];
	arry[left] = arry[right];
	arry[right] = tmp;
}

void QuickSort_On(int* arry,int left,int right)
{
	int i,last;
	if(left >= right)
		return ;
	swap(arry,left,(left+(right-left)/2));
	last = left;
	for(i = left +1;i <= right;++i)
	{
		if(arry[i] < arry[left])
			swap(arry,++last,i);
	}
	swap(arry,left,last);
	QuickSort_On(arry,left,last - 1)  ;         
	QuickSort_On(arry,last +1,right);

}



//歸并排序：利用樹的分支然后在利用區(qū)間的整合，實(shí)現(xiàn)排序完成。
//每次我們確定一個(gè)區(qū)間（n/2），然后不斷進(jìn)行2分的拆分。
//在沒2個(gè)區(qū)間中我們進(jìn)行比較排序，對(duì)每個(gè)區(qū)間的首部進(jìn)行比較，然后規(guī)整到我們需要保存的數(shù)組中。
//最后我們通過不斷的拆分，不斷地歸并復(fù)制，就可以出現(xiàn)相對(duì)的排序序列了。
//0（nlogn）,0（n）
void Merge(int* arry,int* dest,int begin1,int end1,int begin2, int end2)
{
	int index = begin1;
	while(begin1 <= end1 && begin2 <= end2)
	{
		if(arry[begin1] < arry[begin2])
		{
			dest[index++] = arry[begin1++];
		}
		else
		{
			dest[index++] = arry[begin2++];
		}
	}

	if(begin1 <= end1)
	{
		while(begin1 <= end1)
		{
			dest[index++] = arry[begin1++];
		}
	}

	else
	{
		while(begin2 <= end2)
			dest[index++] = arry[begin2++];
	}
}

void _Merge(int* arry,int* dest, int left,int right)
{
	//因?yàn)槭亲箝]右開。
	int mid = left+((right - left) /2);
	if(left < right -1)
	{
		
		//int mid = left+((right - left)>>1);
		_Merge(arry,dest,left,mid);
		_Merge(arry,dest,mid+1,right);

		Merge(arry,dest,left,mid,mid+1,right);

		//memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
	}
	Merge(arry,dest,left,mid,mid+1,right);
	memcpy(arry+left,dest+left,sizeof(int)* (right - left +1));
}

void MergeSort(int *arry,size_t size)
{
	int* dest = new int[size];
	_Merge(arry,dest,0,size-1);
	//memcpy(arry,dest,sizeof(int)* (11));
	delete[] dest;
}

總結(jié)：

創(chuàng)新互聯(lián)公司是一家專注于做網(wǎng)站、網(wǎng)站設(shè)計(jì)與策劃設(shè)計(jì),和平網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)十載,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:和平等地區(qū)。和平做網(wǎng)站價(jià)格咨詢:18982081108

  其中時(shí)間復(fù)雜度為nlogn的有快速排序，歸并排序，堆排序。其中快速排序最壞的情況是n^2,其余都是n^2,希爾排序介于n-n^2之間。

  對(duì)于穩(wěn)定性來說，冒泡排序，插入排序，歸并排序是穩(wěn)定的，其他的排序在不同的情況下穩(wěn)定性會(huì)不同。

  對(duì)于空間復(fù)雜度來說，快速排序的空間復(fù)雜度是0（logn），歸并排序是0（n）

下面是只能在限定條件里面使用的基數(shù)排序和計(jì)數(shù)排序：

計(jì)數(shù)排序:時(shí)間復(fù)雜度:O(N), 空間復(fù)雜度O(最大數(shù)-最小數(shù))

基數(shù)排序:時(shí)間復(fù)雜度:O(N*位數(shù))，空間輔助度O(N)

//基數(shù)排序：利用哈希桶原理把數(shù)據(jù)排序，可選擇從低位到高位或從高位到低位
//利用稀疏矩陣壓縮存儲(chǔ)進(jìn)行數(shù)據(jù)定位
int  GetDigit(int* arr, size_t size)
{
    int maxDigit = 1;
    int maxNum = 10;
    for (int i = 0; i < size; ++i)
    {
        if (arr[i] >= maxNum)
        {
            int count = maxDigit;
            while (maxNum <= arr[i])
            {
                maxNum *= 10;
                ++count;
            }
            maxDigit = count;
        }
    }
    return maxDigit;
}
void LSDSort(int* arr, size_t size)//從低位開始排  MSD從高位開始排
{
    int counts[10] = { 0 };//存位數(shù)對(duì)應(yīng)數(shù)據(jù)個(gè)數(shù)
    int startCounts[10] = { 0 };
    int *bucket = new int[size];
    int digit = 1;//表示先取各位
    int maxDigit = GetDigit(arr, size);
    int divider = 1;//除數(shù)
    while (digit++ <= maxDigit)
    {
        memset(counts, 0, sizeof(int) * 10);
        memset(startCounts, 0, sizeof(int) * 10);
        for (int i = 0; i < size; ++i)
            counts[(arr[i]/divider)% 10]++;
        for (int i = 1; i < 10; ++i)
            startCounts[i] = startCounts[i - 1] + counts[i - 1];
        for (int i = 0; i < size; ++i)
        {
            bucket[startCounts[(arr[i] / divider) % 10]++] = arr[i];
        }
        divider *= 10;
        memcpy(arr, bucket, sizeof(int)*size);
    }
    memcpy(arr, bucket, sizeof(int)*size);
    delete[] bucket;
}
 
//計(jì)數(shù)排序
void CountSort(int *arr, size_t size,int len)
{
    int* bitMap = new int[len];
    memset(bitMap, 0, sizeof(int)*len);
    for (int i = 0; i < size; ++i)
    {
        int index = arr[i] >>5;//除以32
        int count = arr[i] % 32;
        bitMap[index] |= (1 << count);
         
    }
    int index = 0;
     
    for (int i = 0; i < len; ++i)
    {
        int count = 0;
        while (count <32&&index<size )
 
        {
            if (bitMap[i] & (1 << count))
                arr[index++] = i * 32 + count;
            ++count;
        }
    }
    delete[] bitMap;
}

這兩個(gè)排序的使用環(huán)境只能夠在特定的條件下使用，所以沒有納入常規(guī)的排序手法中，但是可以看出他的效率十分驚人。

本文題目：【C/C++】排序總結(jié)
本文網(wǎng)址：http://chinadenli.net/article0/jhjeio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計(jì)、網(wǎng)頁設(shè)計(jì)公司、網(wǎng)站設(shè)計(jì)、自適應(yīng)網(wǎng)站、虛擬主機(jī)、移動(dòng)網(wǎng)站建設(shè)

廣告

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