排序小結(jié) sort

排序小結(jié)

排序算法是基礎(chǔ)之基礎(chǔ)。在這里小結(jié)一下。方便自己查閱和學習。

1.冒泡排序(BubbleSort)

思想：比較相鄰的兩個元素，如果前面的元素大于后面的元素，交換之。

思路：采用雙層循環(huán)。外循環(huán)控制要處理多少趟。里面循環(huán)用來做元素的交換操作。注意上下界。

穩(wěn)定性：穩(wěn)定

時間復雜度：O(n2)

void bubbleSort(int a[], int size)
{
	int tmp;
	for (int i = 0; i < size; i++)
	{	//每一趟都會把最大的元素放入最右邊的位置
		//最右邊的位置會一點點往左移動
		for (int j = 0; j < size - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
	}
}

2.快速排序(quickSort)

思想：找到第一個元素的最終位置，然后對數(shù)組進行分割，對左邊的進行快排，對右邊的進行快排。

思路：采用遞歸，需要一個輔助函數(shù)findPos()來找到某一個元素的最終位置。

穩(wěn)定性：不穩(wěn)定

時間復雜度：有時O(nlogn),最壞情況是已經(jīng)排好序，這樣時間復雜度為O(n2)

偽算法

/*

 * 快速排序（偽算法） 2016-08-14 11:01:34

 * 1.先找到第一個元素的最終位置

 * 2.對第一個元素的最終位置之前的元素，進行快速排序。

 * 3.對第一個元素的最終位置之后的元素，進行快速排序。

 *

*/

int findPos(int a[],int low,int high)
{	
	int val = a[low];
	while(low < high)
	{
		//因為val取的是最前面的值，所以先從后往前遍歷比較
		while(low < high && a[high] >= val)
			high--;
		a[low] = a[high];//將后面較小值賦值給前面已經(jīng)做好備份的位置上
		//然后從前往后遍歷比較
		while(low < high && a[low] <= val)
			low++;
		a[high] = a[low];//將前面較大值賦值給后面已經(jīng)做好備份的位置上
	}
	a[low] = val;
	return low;
}

void quickSort(int a[],int low,int high)
{
	if(low < high)
	{
		int pos = findPos(a,low,high);
		quickSort(a,low,pos-1);
		quickSort(a,pos+1,high);
	}
}

3.直接插入排序(insertSort)也叫選擇插入排序

思想：將第i個元素插入到前面i-1個已排好序的記錄中。直到所有的元素都排一次。

思路：見偽算法

穩(wěn)定性：穩(wěn)定

時間復雜度：O(n2)

偽算法

/*

* 插入排序（偽算法） 2016-08-14 12:23:09

* 1. 將相鄰的兩個元素比較，如果前面的數(shù)大于后面的數(shù)，則交換。

*    直到找到前面的數(shù)小于后面的，就把這個值插入到這個位置。

* 2. 循環(huán)1，直到所有的元素都有序排列。

*

*/

void insertSort(int a[], int size)
{
	int i, j, tmp;
	for (i = 0; i < size; i++)
	{
		tmp = a[i];
		for (j = i - 1; j >= 0 && a[j] > tmp; j--)
		{
			a[j+1] = a[j];
		}
		a[j + 1] = tmp;
	}
}

4.選擇排序(selectSort)

思想：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在待序列的起始位置。 

思路：見偽算法

穩(wěn)定性：不穩(wěn)定

時間復雜度：O(n2)

偽算法

/*

* 選擇排序（偽算法） 2016-08-14 13:08:50

* 1. 工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在待序列的起始位置。 

* 2. 循環(huán)1，直到全部待排序的數(shù)據(jù)元素排完。

*

*/

void selectSort(int a[], int size)
{
	int currentSmallIndex;//記錄待排序隊列中最小元素的下標
	int tmp;//記錄最小元素的大小
	for (int i = 0; i < size; i++)
	{
		tmp = a[i];
		currentSmallIndex = i;
		for (int j = i + 1; j < size; j++)
		{
			if (a[j] < tmp)
			{
				currentSmallIndex = j;
				tmp = a[j];
			}
		}
		a[currentSmallIndex] = a[i];
		a[i] = tmp;
	}
}

5.歸并排序(mergeSort)

思想：將數(shù)組遞歸分成2半，知道數(shù)組的長度為1，然后將分成2半的數(shù)組合并。

思路：需要使用輔助函數(shù)merge()來合并

穩(wěn)定性：穩(wěn)定

時間復雜度：O(n2)

偽算法

/*

1.將數(shù)組分成左右兩半

2.遞歸1，直道只剩1個元素的時候，然后合并。

 */

void merge(int a[], int start, int end)
{
	int mid = (start + end) / 2;
	int left, right;
	int * temp = new int[end - start + 1];

	int k = 0;//臨時數(shù)組的下標
	left = start;
	right = mid + 1;

	while (left <= mid && right <= end)
	{
		while ((left <= mid && right <= end) && (a[left] < a[right]))
			temp[k++] = a[left++];

		while ((left <= mid && right <= end) && (a[right] < a[left]))
			temp[k++] = a[right++];
	}

	while (left <= mid)
		temp[k++] = a[left++];

	while (right <= end)
		temp[k++] = a[right++];

	//將臨時數(shù)組中的元素，找到原數(shù)組的位置，按位賦值過去。
	//這里需要注意原數(shù)組的起始位置是start，而不是0
	for (int i = start, k = 0; i <= end; i++, k++)
		a[i] = temp[k];

	delete[] temp;
}

void mergeSort(int a[], int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		mergeSort(a, start, mid);	//左數(shù)組合并排序
		mergeSort(a, mid + 1, end);	//右數(shù)組合并排序
		merge(a, start, end);		//整體排序
	}
}

排序總結(jié)未完待續(xù)。

2016-08-14 16:11:27