一排序的概念

二常見的排序演算法

(1)插入排序

（2）選擇排序

（3）交換排序

（4）歸并排序

三插入排序

（1）直接插入排序

1.直接插入排序的思想

2.直接插入排序的思想圖解

3.直接插入排序的代碼及運行結果

4.直接插入排序總結

(2)希爾排序

1.希爾排序演算法思想

希爾排序就是將待排序的資料進行分組，然后對每一組進行直接插入排序，達到預排序的效果使得待排序的資料接近有序，然后再次分組，每一個都是使分組間距減小，當分組的間距為一的時候，希爾排序完成，

2.希爾排序思想思想圖解

3.希爾排序的代碼及運行結果，

4.希爾排序總結

四選擇排序

（1）直接選擇排序

1.直接選擇排序的演算法自思想

2.直接選擇排序的思想圖解

3.直接選擇排序代碼及運行結果

4.直接選擇排序總結：

（2）堆排序

1.堆排序的思想及圖解

2.堆排序的代碼及運行結果，

3.堆排序總結

四交換排序

（1）冒泡排序

1.冒泡排序的思想

2.冒泡排序思想圖解

3.冒泡排序的代碼及運行結果

（2）快速排序

1.快速排序的思想

2快速排序的思想圖解

3.快速排序的代碼及運行結果

4.快速排序總結

<1>快速排序的整體應用場景比較好，

<2>時間復雜度：O(N*logN)，

<3>空間復雜度：O(1)，

<4>穩定性：不穩定，

五歸并排序

1 歸并排序

1.歸并排序的思想

2.歸并排序的思想圖解?

3.歸并排序代碼及運行結果

4.歸并排序總結

六各排序演算法性能測驗

七排序演算法總結

一排序的概念

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起操作

二常見的排序演算法

(1)插入排序

1.直接插入排序

2.希爾排序

（2）選擇排序

1.直接選擇排序

2.堆排序

（3）交換排序

1.冒泡排序

2.快速排序

（4）歸并排序

1.歸并排序

三插入排序

（1）直接插入排序

1.直接插入排序的思想

當一個陣列中的前m數有序時，j將第m+1個數插入到自己合適的位置，是這個新的序列有序，

2.直接插入排序的思想圖解

這里以升序為例，我們假定第一個數有序，第二個數開始從后往前找，找到第一個比當前這個數小的數的時候，就插入的這個數的后面，

3.直接插入排序的代碼及運行結果

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i ];
		int j = i;
		for (j = i; j > 0; j--)
		{
			if (a[j - 1] > temp)
			{
				a[j ] = a[j-1];

			}
			else
			{
				break;
			}
		}
		a[j] = temp;
	}
}

void PrintArry(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestInsertSort()
{
	int arr[] = { 5,2,4,6,1,3 };
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}
int main()
{
	TestInsertSort();
	return 0;
}

4.直接插入排序總結

<1>待排序的資料越接近有序，直接插入排序的效率越高，

<2>時間復雜度：O(n^2).

<3>空間復雜度：O(1).

<4>穩定性：穩定，

(2)希爾排序

1.希爾排序演算法思想

希爾排序就是將待排序的資料進行分組，然后對每一組進行直接插入排序，達到預排序的效果使得待排序的資料接近有序，然后再次分組，每一個都是使分組間距減小，當分組的間距為一的時候，希爾排序完成，

2.希爾排序思想思想圖解

3.希爾排序的代碼及運行結果，

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i ];
		int j = i;
		for (j = i; j > 0; j--)
		{
			if (a[j - 1] > temp)
			{
				a[j ] = a[j-1];

			}
			else
			{
				break;
			}
		}
		a[j] = temp;
	}
}

void TestShellSort()
{
	int arr[] = { 8,5,2,4,3,6,1,3 };
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

4.希爾排序總結

<1>希爾排序是對直接插入排序的總結

<2>時間復雜度：O(N)~O(N^2)

<3>空間復雜度：O(1);

<4>穩定性：不穩定；

四選擇排序

（1）直接選擇排序

1.直接選擇排序的演算法自思想

在待排序的陣列中找對找出最大的資料，放在陣列的最后面，找到最小的資料放在陣列的最后面

以此找次小的和次大的，直到陣列有序

2.直接選擇排序的思想圖解

3.直接選擇排序代碼及運行結果

void SelectSort(int* a, int n)
{
	int begin = 0,end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		   if (a[i] <a[mini])
			{
				mini = i;
			}
		}
		if (begin == maxi)
			maxi = mini;
		Swap(&a[begin],&a[mini]);
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;

	}
	
}

void TestSelectSort()
{
	int arr[] = { 8,5,2,4,3,6,1,3 };
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

4.直接選擇排序總結：

<1>直接選擇排序的思想簡單，但是效率不好，實際中很少使用

<2>時間復雜度：O（N^2);

<3>空間復雜度O(1)

<4>穩定性：不穩定

（2）堆排序

1.堆排序的思想及圖解

利用堆的特性，就可以堆一組資料進行建堆，從而達到排序的效果，怎樣才能使得一組無序的資料在邏輯上呈現堆的結構呢？不難發現，當一個完全二叉樹的左子樹和右子樹都是堆的時候，就可以利用向下滲透的方法將這棵樹，變成堆，

這里以小堆為例，當一個完全二叉樹的左子樹和右子樹都是小堆時候，用父親節點和兒子節點中最小的比較，若兒子節點小于父親節點，就將兒子節點和父親節點交換，

向下滲透的程序如圖

有了向下滲透的演算法之后，就可以將建小堆采用分治的演算法建堆，通過觀察，可以發現需要從最后一個非葉子節點開始建堆，而最后一個非葉子節點恰好是最后一個節點的父親節點，這樣就可以使用遞回的思想進行建堆，注：想要排升序就建大堆，排降序就建小堆，

以升序為例，建大堆之后將最后一個節點的和第一個節點交換，然后使用向下滲透演算法進行調整，直到待排序資料排序完成，

2.堆排序的代碼及運行結果，

//向下調整
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		
		if (child+1<n&&a[child + 1] >a[child])
		{
			child = child + 1;
		}
		if ( a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			
		}
		parent = child;
		child = parent * 2 + 1;

	}
}
void HeapSort(int* a, int n)
{
	//建堆
	int root = (n - 1) / 2;
	while (root>=0)
	{
		AdjustDwon(a, n, root);
		
		root--;
	}
	//排序
	while (n >0)
	{
		Swap(&a[n-1], &a[0]);
		n--;
		AdjustDwon(a, n, 0);
	}
}

void TestHeapSort()
{
	
	int arr[] = { 3,5,2,4,3,6,1,8 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

3.堆排序總結

<1>.堆排序利用堆的特點來選數，效率就高很多，

<2>時間復雜度：O（N^logN）.

<3>空間復雜度：O(1).

<4>穩定性：不穩定，

四交換排序

（1）冒泡排序

1.冒泡排序的思想

冒泡排序是從第一個數開始向后比較，遇到比這個數大的（小的）進行交換，這樣就可以使最大的（最下的）到最后一個位置，多次進行就可以實作排序，

2.冒泡排序思想圖解

3.冒泡排序的代碼及運行結果

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i-1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

void TestBubbleSort()
{
	int arr[] = { 25,6,56,24,9,12,55 };
	BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

（2）快速排序

1.快速排序的思想

任取排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該程序，直到所有元素都在相應的位置，

2快速排序的思想圖解

3.快速排序的代碼及運行結果

快速排序有三種遞回的方法

1.挖坑法

挖坑法就是，找待排序資料中的某一個資料作為基準值（一般是第一個或者最后一個），這里以第一個為例，讓基準值所在的位置作為坑，從資料的嘴右邊開始找，若出現比基準值小的，將找到的這個值填入坑中，找到的值的位置作為新的坑，同時左邊找比基準值大的填入坑中，找到的值的位作為行的坑，

2.左右指標法

左右指標法就是，右邊的指標找小于基準值的資料，找到之后于基準值所在的位置交換，這樣基準值就來到了右邊指標的位置，再從左邊開始找第一個大于基準值的資料，基準值所處的位置的資料交換，重復這個程序，直到，左右指標相遇，

3.前后指標法

前后指標法就是，兩個指標一前一后，前后兩個指標同時向前走，當第一次遇到大于基準值的資料時，后面的指標停下來，前面的指標繼續向前走，當前面的指標遇到比基準值小小的資料時，前面的指標所在的位置的資料于后一個指標所在位置的下一個位置的資料交換，直到，前面的指標將真個待排序資料遍歷完，

//三數取中
int GetMInd(int a, int b, int c)
{
	if (a > b)
	{
		if (c > a)
			return a;
		else if (b > c)
			return b;
	}
	else
	{
		if (c > b)
			return b;
		else if (a > c)
			return c;
	}

}
//挖坑法
int QuickSortByPivo(int* a, int left, int right)
{
	int keyi = GetMInd(left, (left + right) / 2, right);
	int pivo = keyi;
	int begin = left;
	int end = right;
	int key = a[keyi];
	while (begin < end)
	{
		if (begin < end && a[end] <= key)
		{
			a[pivo] = a[end];
			pivo = end;
			begin++;
		}
		if (begin < end && a[begin] >= key)
		{
			a[pivo] = a[begin];
			pivo = begin;
			end--;
		}

	}
	a[pivo] = key;
	return pivo;
	
}
//左右指標法
int QuickSortByLR(int* a, int left, int right)
{
	int keyi = GetMInd(left, (left + right) / 2, right);//三數取中
	Swap(&a[keyi], &a[left]);
	int key = a[left];
	while (left < right)
	{
		while (left<right&&a[right] >= key)
		{
			right--;
		}
		Swap(&a[right], &a[left]);
		while (left<right&&a[left] <= key)
		{
			left++;
		}
		Swap(&a[left], &a[right]);
		
	}
	return right;
	
}
//前后指標法
int QuickSortByPC(int* a, int left, int right)
{

	int prev = left - 1;
	int cur = left;
	int key = a[left];
	while (cur <=right)
	{
		if (a[cur] <=key )
		{
			if (cur - prev == 1)
			{
				cur++;
				prev++;
			}
			else
			{
				prev++;
				Swap(&a[cur], &a[prev]);
				cur++;
			}
		}
		else
		{
			cur++;
		}
	}
	Swap(&a[prev], &a[left]);
	return prev;
}


void QuickSort(int* a, int left, int right)
{
	if (left >=right)
		return;
	
	//int pivo = QuickSortByLR(a, left, right);
	//int pivo = QuickSortByPivo(a, left, right);
	int pivo = QuickSortByPC(a, left, right);
	QuickSort(a,left, pivo - 1);
	QuickSort(a,pivo + 1, right);
}

void TestQuickSort()
{
	int arr[]={ 49, 38, 65, 97, 76, 13, 27, 49 };
	QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) -1);
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

4.快速排序總結

<1>快速排序的整體應用場景比較好，

<2>時間復雜度：O(N*logN)，

<3>空間復雜度：O(1)，

<4>穩定性：不穩定，

五歸并排序

1 歸并排序

1.歸并排序的思想

歸并排序是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

2.歸并排序的思想圖解

3.歸并排序代碼及運行結果

void _MergeSort(int* a,int*temp, int left, int right)
{
	int mind = (left + right) / 2;
	int begin1 = left, end1 = mind;
	int begin2 = mind + 1, end2 = right;
	if (left >= right)
	{
		return;
	}
	_MergeSort(a, temp, begin1, end1);
	_MergeSort(a, temp, begin2, end2);
	
		int index = left;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (a[begin1] < a[begin2])
			{
				temp[index++] = a[begin1++];
			}
			else
			{
				temp[index++] = a[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			temp[index++] = a[begin1++];
		}
		while (begin2 <= end2)
		{
			temp[index++] = a[begin2++];
		}
		for (int i = left; i <= right; ++i)
		{
			a[i] = temp[i];
		}

}

void MergeSort(int* a, int n)
{
	int right = n - 1;
	int left = 0;
	int* temp =(int*) malloc(sizeof(int) * n);
	assert(temp);
	_MergeSort(a, temp, 0, n - 1);
	free(temp);
}

void TestMergeSort()
{
	int arr[] = { 10,6,7,1,3,9 ,4,2};
	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

4.歸并排序總結

1. 歸并的缺點在于需要 O(N) 的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問

題，

2. 時間復雜度： O(N*logN)

3. 空間復雜度： O(N)

4. 穩定性：穩定

六各排序演算法性能測驗

void TestOP()
{
	int N = 100000;
	srand((unsigned)time(NULL));
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) *N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}

七排序演算法總結

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/304912.html

標籤：java

上一篇：??酷炫漂亮回應式風景旅游網頁設計??（國慶旅游主題-HTML+CSS+JavaScript/javaweb前端大作業）(二)

下一篇：二叉樹的遍歷（遞回+迭代）

七大排序演算法

一 排序的概念

二 常見的排序演算法

(1)插入排序

（2）選擇排序

（3）交換排序

（4）歸并排序

三 插入排序

（1）直接插入排序

1.直接插入排序的思想

2.直接插入排序的思想圖解

3.直接插入排序的代碼及運行結果

4.直接插入排序總結

<1>待排序的資料越接近有序，直接插入排序的效率越高，

<2>時間復雜度：O(n^2).

<3>空間復雜度：O(1).

<4>穩定性：穩定，

(2)希爾排序

1.希爾排序演算法思想

希爾排序就是將待排序的資料進行分組，然后對每一組進行直接插入排序，達到預排序的效果使得待排序的資料接近有序，然后再次分組，每一個都是使分組間距減小，當分組的間距為一的時候，希爾排序完成，

2.希爾排序思想思想圖解

3.希爾排序的代碼及運行結果，

4.希爾排序總結

四 選擇排序

（1）直接選擇排序

1.直接選擇排序的演算法自思想

2.直接選擇排序的思想圖解

3.直接選擇排序代碼及運行結果

4.直接選擇排序總結：

（2）堆排序

1.堆排序的思想及圖解

2.堆排序的代碼及運行結果，

3.堆排序總結

四 交換排序

（1）冒泡排序

1.冒泡排序的思想

2.冒泡排序思想圖解

3.冒泡排序的代碼及運行結果

（2）快速排序

1.快速排序的思想

2快速排序的思想圖解

3.快速排序的代碼及運行結果

4.快速排序總結

<1>快速排序的整體應用場景比較好，

<2>時間復雜度：O(N*logN)，

<3>空間復雜度：O(1)，

<4>穩定性：不穩定，

五 歸并排序

1 歸并排序

1.歸并排序的思想

2.歸并排序的思想圖解

3.歸并排序代碼及運行結果

4.歸并排序總結

六 各排序演算法性能測驗

七 排序演算法總結

一排序的概念

二常見的排序演算法

三插入排序

四選擇排序

四交換排序

五歸并排序

六各排序演算法性能測驗

七排序演算法總結