八大排序 (上)

(文章目錄)

一、 直接插入排序

1.概念

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

2.直接插入排序的實作

void insertsort(int* a, int sz)//直接插入排序   [0 end]有序，插入end+1位置的值讓[ 0 end+1]也有序
{
	int i = 0;//假設我們要排升序
	for (i = 0; i < sz - 1; i++)//i不能取到sz-1 否則tmp就會造成越界通路
	{
		int end = i;
		int tmp = a[end + 1];//後一個資料
		while (end >= 0)
		{
			if (a[end] > tmp)//如果數組中的資料大于tmp
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;//找到比tmp小的就結束循環
			}
		}
		a[end + 1] = tmp;//為了防止tmp比所有資料都小這種情況發生
	}
	
}
           

直接插入排序的時間複雜度

二、 希爾排序

1.概念

思想為 ：先標明一個整數，把 待排序檔案中所有記錄分組，所有距離内的記錄在同一組中，再對每一組内的記錄進行排序，重複分組和排序， 直到=1時結束.

希爾是直接插入排序的優化

1.先進行預排序,讓數組接近有序

2.直接插入排序

此時發現： 多組間隔為gap的預排序，gap由大變小

gap 越大，大的數越快到後面，小的數越快到前面

gap越大，預排完，越不接近有序，

gap越小，預排完，越接近有序

當gap=1時，就時直接插入排序

2. 希爾排序的實作

void shellsort(int* a, int n)//希爾排序
{
	int i = 0;
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1; //間隔為gap的多組資料同時排
		for (i = 0; i < n - gap; i++)//如果gap換成1  那就是直接插入排序
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end = end - gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
           

3. 希爾排序的時間複雜度

1. gap=n , gap=gap/3+1 即 n=n/3+1

   假設 x為操作次數 3^x=n+1 x=log 3 n+1

   時間複雜度為 O(log 3 N)

2.預排序會使數組接近有序 ,如gap=1 時 ，就為直接插入排序，時間複雜度為O(N)

希爾排序 整體時間複雜度為O(N *log 3 N )

三、 直接選擇排序

1.直接選擇排序的實作

void selectsort(int arr[], int n)//直接選擇排序
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{

		int max = begin;
		int min = begin;
		int i = 0;
		for (i = begin; i <= end; i++)
		{
			if (arr[i] < arr[min])
			{
				min = i;//通過交換找到最大值坐标
			}
			if (arr[i] > arr[max])
			{
				max = i;//通過交換找到最小值坐标
			}
		}
		swap(&arr[begin], &arr[min]);//通過坐标将最小值交換到第begin個
		if (begin == max)
		{
			max = min;
		}
		swap(&arr[end], &arr[max]);//通過坐标将最大值交換到第end個
		begin++;
		end--;
	}
}
           

2.注意事項

3.直接選擇排序的時間複雜度

直接選擇排序 ,無論 數組處于 有序 （最好情況下），還是無序 (最壞情況下) 都需要将整個數組周遊一遍 ，

時間複雜度為O(N^2)

四、 堆排序

點選這裡 :堆排序詳解

五、冒泡排序

1.冒泡排序的實作

void bubblesort(int* a, int sz)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz - 1; i++)// i代表趟數  i在倒數第二次就已經把數組排好了 
	{
		int exchange = 0;
		for (j = 0; j < sz - 1 - i; j++)//j代表每趟的對數 
		{
			if (a[j] > a[j + 1])
			{
				int tmp = 0;
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange = 1;
			}
		}
		if (exchange == 0)//說明周遊一遍都沒有進行比較，則有序
		{
			break;
		}
	}
}
           

2.冒泡排序的時間複雜度

正常情況下:

第一趟時，共比較 n-1次 ，

第二趟時，共比較n-2 次，

第n-1趟時，共比較1次

操作次數為: n-1+n-2+n-3+.......+1=n(n-1)/2

通過大O漸進法省略 ,時間複雜度為O(N^2)

最好情況下:

數組為有序時 ，如 ： 1 2 3 4 5

正好排升序，周遊一遍後發現并沒有進入交換中，exchange==0則跳出循環。

時間複雜度為O(N)

3.冒泡排序與直接插入排序誰更好？