天天看點

七大排序算法詳解【資料結構】

七大排序算法詳解【資料結構】

算法穩定性:

通俗了解------A(1)=80;A(2) = 80;

排序前A(1)在A(2)前,排序後A(1)還在A(2)前則穩定,否則不穩定

代碼中使用到的幾個函數和指針:

typedef int(*Compare)(int left, int right);		//函數指針,可靈活選擇排序的順序
int Less(int left, int right)
{
	return left < right;
}

int Greater(int left, int right)
{
	return left > right;
}


void Swap(int *left, int* right)
{
	int tmp = *left;
	*left = *right;
	*right = tmp;
}
           

冒泡排序:多在資料規模較小的時候使用        時間複雜度O(n^2)   空間複雜度O(1)    穩定排序

思想:

每次循環比較相鄰的兩個元素的大小,将較大(小)的往後冒,每一趟下來最後一個元素都是最大的,每排一趟,最後的元素下标向前移一位,最終完成排序。

void BubbleSort(int array[], int size, Compare com)
//兩兩進行比較,将大的放置到後面,第一趟下來最後的值就是最大的值,依次類推,完成排序
{
	int i = 0;
	int j = 0;
	int flag = 0;					//設定标記,優化冒泡
	for (; i < size - 1; i++)		//最後一個元素不需要冒泡
	{
		int flag = 0;
		for (j = 0; j < size - i - 1; j++)
		{
			if (com(array[j], array[j + 1]))
			{
				Swap(&array[j], &array[j + 1]);
				flag = 1;
			}
		}
		if (flag != 1)
		{
			break;
		}
	}
}
           

選擇排序://元素重複較多時間複雜度O(n^2)   空間複雜度O(1)   不穩定

思想:

内層循環找到最大的元素,标記下标,外層循環控制将最大的元素與最後一個位置的元素進行交換,直到有序

void SelectSort(int array[], int size, Compare com)			//初級版本
{
	//先預設的把首位置下标為最小值下标。然後周遊後面的數字,出現比這個值還小的數
	//就把那個數的下标賦給最小值下标。
	//循環周遊直到有序
	int i = 0;
	int j = 0;
	int min = 0;
	for (i = 0; i < size - 1; i++)			
	{
		min = i;							//預設首元素最小
		for (j = i + 1; j < size; j++)
		{
			if (com(array[min], array[j])) //如果有數比m下标中的數還小,就把這個數的下标放到min中
			{
				min = j;
			}
		}
		if (min != i)						//若是同一位置,不需要交換
			Swap(&array[i], &array[min]);
	}
}
           
void SelectSort3(int array[], int size)		//優化版
{
	int i = 0;
	int maxPos = 0;		//标記最大的
	int minPos = 0;		//标記最小的
	int begin = 0;
	int end = size - 1;
	while (begin < end)
	{
		i = begin;
		minPos = begin;
		maxPos = begin;
		for (; i <= end; i++)		//周遊分别找到最大的和最小的下标
		{
			if (array[i] < array[minPos])
				minPos = i;
			if (array[i] > array[maxPos])
				maxPos = i;
		}
		if (minPos != begin)				//最小的不在最開始的位置
		{
			Swap(&array[minPos], &array[begin]);
		}
		if (maxPos == begin)
		{
			maxPos = minPos;
		}
		if (maxPos != end)					//最大的不在最後的位置
		{
			Swap(&array[maxPos], &array[end]);
		}
		begin++;
		end--;
	}
}
           

插入排序:// 資料元素接近有序、資料量少時間複雜度O(n^2)空間複雜度O(1)穩定

思想:

預設第1個元素前的元素都已經有序,将之後的元素全部插入到前面

插入方法:

标記待插數,與前面的元素比較,找到插入的位置,将要插入位置的元素全向後搬移,騰出位置插入待插數,依次循環直到有序

void InsertionSort(int array[], int size, Compare com)		//普通版
{
	int i = 0;
	int end = 0;
	int tmp = 0;
	for (i = 1; i < size; i++)
	{
		tmp = array[i];					//待測數
		end = i - 1;						//待測數的前一個數即是有序數的最後一個數
		while(end >= 0 && com(array[end], tmp)) //找到要插入的位置
		{
			array[end + 1] = array[end];	//不是要插入的位置,元素向後搬移
			end--;
		}
		array[end + 1] = tmp;				//插入
	}
}
           
void BinInsSort(int array[], int size)		//優化版,二分查找法
{
	int i = 0;
	int j = 0;
	int tmp = 0;
	int low = 0;
	int high = 0;
	int mid = 0;
	// 1 2 3 4 5 6 7 8 9 0
	for (i = 1; i < size; i++)
	{
		tmp = array[i];
		low = 0;
		high = i - 1;
		while (low <= high)		// 當up移動到low左側時,結束循環。注意,此處一定要帶有等号,否則排序會失敗(第一次排序可驗證)
		{
			mid = low + (high - low)/2;		//取中
			if (tmp < array[mid])			//當待插入元素小于中間位置的元素時
			{
				high = mid - 1;				//待插入元素應該插在在前半個表中
			}
			else
			{
				low = mid + 1;
			}
		}
		for (j = i - 1; j >= low; j--)		//從要插入元素的位置開始将元素依次搬移
		{
			array[j + 1] = array[j];
		}
		array[low] = tmp;				//插入
	}
}
           

希爾排序://資料元素無序、資料量大時間複雜度O(N^1.3)空間複雜度O(1)不穩定

思想:

分組進行插入排序

先定義一個步長序列,依次遞減至一,然後按照步長将資料分組,所有距離為步長倍數的數分為一組,在組内對資料進行插入排序,步長序列遞減。

void ShellSort(int array[], int size)
{
	int end = 0;
	int tmp = 0;
	int gap = size;
	//生成步長序列
	while(gap > 1)			//gap > 1
	{
		gap = gap / 3 + 1;	//調整步長序列
		int i = gap;
		//插入排序
		for (; i < size; i++)	//i一次走一步直至所有元素都排好序
		{
			tmp = array[i];					//待測數
			end = i - gap;						//有序數列的最後一個元素
			while (end >= 0 && array[end] > tmp) //找到要插入的位置
			{
				array[end + gap] = array[end];	//
				end -= gap;
			}
			array[end + gap] = tmp;				//插入
		}
	}
}
           

堆排序://資料規模較大時

思想:

先将所有元素構成大根堆将堆頂元素和堆最後一個元素交換,交換後重新調整堆為大根堆依次類推直到有序。

函數分為調整部分和排序部分。

void AdjustHeap(int array[], int size, int root, Compare com)//小堆----->向下調整
{

	int child = root * 2 + 1;			//左孩子 

	while (child < size)
	{
		if (child + 1 < size && com(array[child + 1], array[child]))//找到左右孩子中小的,标記為child
		{
			child += 1;
		}
		if (com(array[child], array[root]))				//判斷是否需要交換位置
		{
			Swap(&array[root], &array[child]);
			root = child;
			child = root * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int array[], int size, Compare com)
{
	int end = size - 1;						//标記最後一個結點的下标
	int LastRoot = (size - 2) >> 1;			//最後一個非葉子節點
	while (LastRoot >= 0)					//建堆
	{
		AdjustHeap(array, size, LastRoot, com);
		LastRoot--;
	}
	while (end > 0)							//最後一個節點不交換		//堆的删除
	{
		Swap(&array[0], &array[end]);		//先交換
		AdjustHeap(array, end, 0, com);		//在調整(從end的前一個節點開始調)
		end--;								//在向前移
	}
}
           

快速排序:資料接近有序時快速排序算法不适用,效率低

标記一個關鍵碼,将比關鍵碼小的元素,向前搬移,将比關鍵碼大的元素向後搬移。

優化:

1. 三值取中确定基準值 (傳回中間值的索引)

取第一個元素,最後一個元素,中間的元素判斷大小

2. 當區間比較小時,就可以使用插入排序,直接對這個區間進行排序進而有效減少遞歸次數

Right - left  <  16  -----------------插入排序

int partion(int array[], int left, int right)//雙指針相向移動
{
	int key = array[right - 1];
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		while (begin < end && array[begin] <= key)//從左往右找最大的//begin<end防止在查找的時候begin越界
			begin++;
		while (begin < end && array[end] >= key)	//從右往左找最小的
			end--;
			//找到一個最大的和最小的
		if (begin < end)		//不在同一位置
		{
			Swap(&array[begin], &array[end]);
		}
	}
	//begin 和 end 走到同一位置 ,若不是最後位置交換
	if (begin != right - 1)
	{
		Swap(&array[begin], &array[right - 1]);
	}
	return begin;
}

int partion2(int array[], int left, int right)	//挖坑法
{
	int key = array[right - 1];
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		while (begin < end && array[begin] <= key)//從左往右找最大的//begin<end防止在查找的時候begin越界
			begin++;
		if (begin < end)		//填坑
			array[end] = array[begin];
		while (begin < end && array[end] >= key)	//從右往左找最小的
			end--;
		if (begin < end)
			array[begin] = array[end];
	}
	//begin, end到同一位置
	array[end] = key;	//填最後一個坑
	return begin;
}

int partion3(int array[], int left, int right)//雙支指針前移法
{
	int key = array[right - 1];
	int begin = left - 1;//此處不會發生越界問題,并未通路數組-1處的元素
	int end = left;

	//定義兩個指針一個begin和end,從左往右周遊,end的值小于基準值時讓begin前進一個位置
	//并檢測是否與end為同一位置,若不是則交換位置上的值,end就是檢測所有資料中比基準值小的值
	//利用begin将其向前挪,循環結束時需交換begin位置的元素和基準值
	while(end < right)//end指向目前元素,每次循環都要往前走,直到周遊完序列
	{
		if (array[end] < key)
		{
			//end處的元素小于key,begin前移,并判斷
			begin++;
			if (begin != end)
			{
				Swap(&array[begin], &array[end]);
			}
		}
		end++;
	}

	if (array[++begin] != key)			//此時begin的值一定小于key,begin的下一個元素大于等于key
		//交換begin+1 和最後的元素
		Swap(&array[begin], &array[right - 1]);
	return begin ;
}

void QuickSort(int array[], int left, int right)	//遞歸版本
{
	int div = 0;
	if (left < right)
	{
		div = partion3(array, left, right);
		QuickSort(array, left, div);
		QuickSort(array, div + 1, right);
	}
	
}
           
void QickSortByLoop(int array[], int size)		//非遞歸版本,借助棧
{
	Stack s;
	int left = 0;
	int mid = 0;
	int right = size;
	assert(array);
	if (size <= 1)
	{
		return;
	}
	//用棧儲存每一個待排序子串的首尾元素下标,
	//下一次while循環時取出這個範圍,對這段子序列進行partion操作  
	InitStack(&s);
	PushStack(&s, left);		//左入棧
	PushStack(&s, right);		//右入棧
	while (!StackEmpty(&s))//棧不為空
	{
		right = TopStack(&s);	//右出棧
		PopStack(&s);
		left = TopStack(&s);	//左出棧
		PopStack(&s);
		if (left < right)
		{
			mid = partion3(array, left, right);
			PushStack(&s, left);
			PushStack(&s, mid);
			PushStack(&s, mid + 1);
			PushStack(&s, right);
		}
	}
}
           

歸并排序: 外部排序,适用于資料量大的情況

假設數組A有N個元素,那麼可以看成數組A是又N個有序的子序列組成,每個子序列的長度為1,然後再兩兩合并,得到了一個 N/2 個長度為2或1的有序子序列,再兩兩合并,如此重複,值得得到一個長度為N的有序資料序列為止。

合并算法:即合并兩個有序的子序列,設定兩個指針,p1,p2,将p1,p2所指向元素當中值較小的不斷複制到臨時空間,最後把沒複制完的子序列的剩餘yuan複制到臨時空間

void _MergeData(int* array, int left, int mid, int right, int* tmp)	//左閉右開區間
{
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid;
	int end2 = right;
	int index = left;
	//兩個分組中都有元素時
	while (begin1 < end1 && begin2 < end2)
	{
		if (array[begin1] <= array[begin2])		//将兩部分元素中較小的指派到臨時空間中
		{
			tmp[index++] = array[begin1++];
		}
		else
		{
			tmp[index++] = array[begin2++];
		}
	}
	while (begin1 < end1)			//将剩餘元素指派到臨時空間中
		tmp[index++] = array[begin1++];
	while (begin2 < end2)
		tmp[index++] = array[begin2++];
}

void _MergeSort(int* array, int left, int right, int* tmp)
{
	//目前分組中隻有一個元素時歸并結束
	if (right - left > 1)	//遞歸出口
	{
		int mid = left + ((right - left) >> 1); //取中間值
		_MergeSort(array, left, mid, tmp);	//拆分
		_MergeSort(array, mid, right, tmp);
		_MergeData(array, left, mid, right, tmp);	//歸并
		memcpy(array + left, tmp + left, sizeof(array[0])*(right - left));//将目前tmp數組中的元素拷貝回array
	}
}

void MergeSort(int array[], int size)
{
	int *tmp = (int*)malloc(sizeof(array[0])*size);
	if (NULL == tmp)
	{
		return;
	}
	if (size <= 1)
	{
		return;
	}

	_MergeSort(array, 0, size, tmp);
	free(tmp);
}

void MergeSortNor(int array[], int size)
{
	//設定步長從1開始,每次遞增二倍
	int gap = 1;
	int i = 0;
	int left = 0;
	int right = size;
	int* tmp = (int*)malloc(sizeof(array[0])*size);
	if (NULL == tmp)
	{
		return;
	}
	while (gap < size)
	{
		int mid = left + ((right - left) >> 1);

		for (i = 0; i < size; i += 2 * gap)
		{
			left = i;
			mid = left + gap;
			if (mid > size)		//mid越界
				mid = size;
			right = mid + gap;
			if (right > size)	//right越界
				right = size;
			_MergeData(array, left, mid, right, tmp);	//資料排序
		}
		memcpy(array, tmp, sizeof(array[0])*size);
		gap *= 2;
	}
	free(tmp);
}
           

計數排序:适用于資料量大,但是大小比較集中的資料排序。

1.确定資料大小

2.配置設定适當空間

3.統計資料元素出現次數,将結果儲存至臨時空間

4.資料回收----将tmp中的資料反向放回array數組中

void CountSort(int array[], int size)
{
	int i = 0;
	int MaxValue = array[0];
	int MinValue = array[0];
	int TmpSize = 0;
	int Index = 0;
	//确定大小
	for (i = 0; i < size; i++)
	{
		if (array[i] < MinValue)
		{
			MinValue = array[i];
		}
		if (array[i] > MaxValue)
		{
			MaxValue = array[i];
		}
	}
	//配置設定空間
	TmpSize = MaxValue - MinValue + 1;
	int* tmp = (int*)malloc(sizeof(int)* TmpSize);
	if (NULL == tmp)
	{
		return;
	}
	memset(tmp, 0x00, sizeof(int)*TmpSize);
	//統計每個資料個數,并将其個數放置進tmp的指定位置
	for (i = 0; i < size; i++)
	{
		tmp[array[i] - MinValue]++;
	}
	//資料回收---将tmp數組的資料重新放回array
	i = 0;
	while (i < TmpSize)
	{
		while (tmp[i]--)
		{
			array[Index++] = i + MinValue;
		}
		i++;
	}
	free(tmp);
}
           
七大排序算法詳解【資料結構】

基數排序:

LSD:低關鍵碼優先----從數字的低位到高位依次排序

MSD:高關鍵碼優先---從高高位到低位依次排序

LSD:

得到數組的最大的數的位數,從個位開始,将資料依次放入指定的桶中,再将桶中的元素拷貝回原數組,在次對原數組中的數的高一位進行處理。

統計每個桶中有效元素個數

計算每個桶的起始位址

将元素按照目前位置放入桶中

對元素進行回收--------将桶中元素拷回原數組

七大排序算法詳解【資料結構】

将桶中的資料拷貝回原數組,則會轉化為排序下列資料: 281, 321, 262, 374, 255, 655, 987, 198, 789。再對該組資料按十位進行排序。

七大排序算法詳解【資料結構】

将桶中的資料拷貝回原數組,則會轉化為排序下列資料:321, 255, 655, 262, 374, 281, 987, 789, 198。再對該組資料按百位進行排序。

七大排序算法詳解【資料結構】

最後形成有序資料: 198,255, 262, 281, 321, 374, 655 , 789, 987.

代碼:

void _RadixSortLSD(int array[], int size, int* bucket)		//M位  個數N
{
	int i = 0;
	int bitIdx = 0;
	int bitIdxNum = 0;
	int radix = 1;
	bitIdxNum = GetbitNum(array, size);
	for (bitIdx = 0; bitIdx < bitIdxNum; bitIdx++)
	{
		int count[10] = { 0 };		//有效元素個數
		int addrStart[10] = { 0 };	//起始位址
		//統計每個桶中元素的個數
		for (i = 0; i < size; i++)
		{
			count[array[i] / radix % 10]++;
		}
		//計算每個桶的起始位址
		for (i = 1; i < 10; i++)
		{
			addrStart[i] = addrStart[i - 1] + count[i - 1];
		}
		//将元素按照目前位置放入對應的桶中
		for (i = 0; i < size; i++)
		{
			int bucketNo = array[i]/ radix % 10;	//桶号
			bucket[addrStart[bucketNo]++] = array[i];//先利用桶号計算出起始位址,将元素放入該起始位址處
			//然後目前桶的起始位址+1
		}
		//對元素進行回收
		memcpy(array, bucket, sizeof(array[0])* size);
		radix *= 10;
	}
}
void RadixSort(int array[], int size)
{
	if (size < 2)
	{
		printf("資料量小于2,無需排序!\n");
		return;
	}
	int* bucket = (int*)malloc(sizeof(array[0])*size);
	if (NULL == bucket)
	{
		return;
	}
	_RadixSortLSD(array, size, bucket);
	free(bucket);
}
           

MSD:  此處需借助遞歸思想,先對将資料按最高位的大小放入指定的桶中,然後對每個桶的低位遞歸的進行置桶和拷貝操作。

七大排序算法詳解【資料結構】

代碼:

void _RadixSortMSD(int array[], int left, int right, int* bucket, int bitNum)//高關鍵碼優先,采用遞歸的方式
{
	int i = 0;
	int radix = pow(10, bitNum);
	int count[10] = { 0 };		//有效元素個數
	int addrStart[10] = { 0 };	//起始位址
		
	if (bitNum < 0)
	{
		return;
	}
	//統計每個桶中元素的個數
	for (i = left; i < right; i++)
	{
		count[array[i] / radix % 10]++;
	}
	//計算每個桶的起始位址
	for (i = 1; i < 10; i++)
	{
		addrStart[i] = addrStart[i - 1] + count[i - 1];
	}
	//将元素按照目前位置放入對應的桶中
	for (i = left; i < right; i++)
	{
		int bucketNo = array[i] / radix % 10;	//桶号
		bucket[addrStart[bucketNo]++] = array[i];//先利用桶号計算出起始位址,将元素放入該起始位址處
		//然後目前桶的起始位址+1
	}
	//對元素進行回收
	memcpy(array+ left, bucket, sizeof(array[0])* (right - left));	//拷貝時拷貝到array的對應位置

	for (i = 0; i < 10; i++)//排每個桶元素的低一位
	{
		int begin = addrStart[i] - count[i];//目前桶的起始位址 = 目前桶的位址 - 目前桶的元素個數
		int end = addrStart[i];
		if (begin + 1 >= end)	//目前桶的元素隻有一個或小于1排序下一個桶
		{
			continue;
		}
		_RadixSortMSD(array, begin, end, bucket, bitNum--);
	}
}

void RadixSort(int array[], int size)
{
	if (size < 2)
	{
		printf("資料量小于2,無需排序!\n");
		return;
	}
	int* bucket = (int*)malloc(sizeof(array[0])*size);
	if (NULL == bucket)
	{
		return;
	}
	_RadixSortMSD(array, 0, size, bucket, GetbitNum(array, size) - 1);
	free(bucket);
}
           

繼續閱讀