資料結構與算法之選擇排序

接下來要說的便是選擇排序

選擇排序是冒泡排序的一個變種，但是它沒有冒泡排序對資料有序性那麼敏感，但它在排序過程中比冒泡少了很多的資料交換，是以在資料比較混亂的情況下要比冒泡快。

工作原理：第一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然後再從剩餘的未排序元素中尋找到最小（大）元素，然後放到已排序的序列的末尾。以此類推，直到全部待排序的資料元素的個數為零。選擇排序是不穩定的排序方法。

選擇排序的時間複雜度是O(n^2)，是一種不穩定的算法

算法實作：

1、假設确定最後一個資料為最大值

2、從頭開始周遊這串資料，如果找到比假定的值還要大的數就記錄

3、交換它兩的值

代碼如下：

void select_sort(int* arr,size_t n)
{
	for(int i=n-1;i>0;i--)
	{
		int max = i;
		for(int j=0;j<i;j++)
		{
			if(arr[j] > arr[max])
				max = j;
		}
		if(max != i)
		{
			swap(arr[max],arr[i]);	
		}
	}
}
           

堆排序：https://blog.csdn.net/weixin_43505112/article/details/97516883

插入排序：https://blog.csdn.net/weixin_43505112/article/details/97514627

歸并排序：https://blog.csdn.net/weixin_43505112/article/details/97299733

快速排序：https://blog.csdn.net/weixin_43505112/article/details/97298960

冒泡排序：https://blog.csdn.net/weixin_43505112/article/details/97297043