【C/C++】排序總結

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

//直接排序：指的是設定2個下標/指針。然后從下標1開始進行比較，
//升序情況下：若在前的下標/指針大于當前比較數值。就進行數組的后移。
//直到滿足當前序列值。然后最終將當前比較數值進行替換。
//PS：總有一個指針遍歷比較數組（k，arry[i]）
//時間復雜度為：0（n^2）,空間復雜度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;
	}
}

//希爾排序：在直接排序的基礎上增加分組Gap值，
//利用Gap值，比較對應（len/gap）* i的位置。每個位置代表一個分組
//然后將i的值依次增加到len-gap的位置相當于我已經比較了每個對應分組，使當前序列趨近于有序。
//然后我們縮小gap值的范圍，使其接近于2，證明還需要進行分組排序。
//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;
		}
	}
}

//選擇排序：其實這個排序的思路比較簡單，我們只需要每次遍歷數組
//得到最小/最大（或者2者都選），然后將最大值最小值分別丟到數組的最左端還有最右端然后縮小范圍就可以了。
//然后值得注意的是。我們在同時得出當前最大最小值時候，需要注意
//當前選出的最大值最小值在進行其中一次交換后，會不會將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;
			}
		}
	}
}

//冒泡排序：冒泡排序比較簡單，就不多說了。
//需要注意的是我們可以利用一個標記值來確定我們需不需要進行這一次的冒泡
//如果需要進行冒泡的話我們的標記值就會設置位開關。
//然后我們就可以減少我們所需要排序的次數。
//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個下標/指針,然后我們利用指針選擇法
//將大數與小數集中排列。將我們所選的key值建為關鍵值，大于放左邊，小于放右邊。然后不斷縮小范圍就好了
//提高效率的辦法就是我們可以在當前序列的值小于某個數值的時候我們選擇使用插入排序。
//這可以有效的提高我們排序的效率。
//一前一后只適用于數組。
//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);

	}
}


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


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);

}



//歸并排序：利用樹的分支然后在利用區間的整合，實現排序完成。
//每次我們確定一個區間（n/2），然后不斷進行2分的拆分。
//在沒2個區間中我們進行比較排序，對每個區間的首部進行比較，然后規整到我們需要保存的數組中。
//最后我們通過不斷的拆分，不斷地歸并復制，就可以出現相對的排序序列了。
//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)
{
	//因為是左閉右開。
	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;
}

總結：

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

  對于穩定性來說，冒泡排序，插入排序，歸并排序是穩定的，其他的排序在不同的情況下穩定性會不同。

  對于空間復雜度來說，快速排序的空間復雜度是0（logn），歸并排序是0（n）

下面是只能在限定條件里面使用的基數排序和計數排序：

計數排序:時間復雜度:O(N), 空間復雜度O(最大數-最小數)

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

//基數排序：利用哈希桶原理把數據排序，可選擇從低位到高位或從高位到低位
//利用稀疏矩陣壓縮存儲進行數據定位
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 };//存位數對應數據個數
    int startCounts[10] = { 0 };
    int *bucket = new int[size];
    int digit = 1;//表示先取各位
    int maxDigit = GetDigit(arr, size);
    int divider = 1;//除數
    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;
}
 
//計數排序
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;
}

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