排序算法总结

淩亂°似流年 2022-01-06 04:09 281阅读 0赞

### 1.插入排序算法（附伪代码和C源码） ###

*  **插入排序原理**：从第i=2位开始到数组长度|A|截至。将当前i的值key取出来，从i开始从后往前\[1, i-1\]寻找小于（大于）key的下标且下标不为0，找的同时如果不满足寻找条件，将经历的数整体往后移动，直到不满足条件为止。由于从第二个数开始后保证当前数之前的序列是有序的，最终i=|A|时可满足整个序列有序！
 *  伪代码

INSERTION-SORT(A)
    for i=2 to |A|
    	key = A[i]
    	j = i - 1
    	while j>=0 and A[j] > key
    		A[j+1] = A[j]
    		j = j - 1
    	end
    	A[j+1] = key
    end

*  算法执行过程图  
    ![InsertSort][]
 *  动态过程图

> 出处（请多支持原创，我只是简单搬运）：[https://www.zhihu.com/search?type=content&q=堆排序][https_www.zhihu.com_search_type_content_q]  
> ![在这里插入图片描述][20190625125455307.gif]

*  插入排序

#include <stdio.h>
    int arr[5] = { 10, 4, 2 ,6 ,1 };
    const int arrrlens = 5;
    void PrintArray(int* arr)
    {
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    // InsertSort SourceCode
    void InsertSort(int *arr)
    {
    	for (int ii = 1; ii < arrrlens; ii++)
    	{
    		int key = arr[ii];
    		int jj = ii - 1;
    		while (jj >= 0 && arr[jj] > key)
    		{
    			arr[jj+1] = arr[jj];
    			jj = jj - 1;
    		}
    		arr[jj+1] = key;
    	}
    }
    int main()
    {	
    	PrintArray(arr);
    	InsertSort(arr);
    	PrintArray(arr);
    }

### 2.归并排序算法（附C源码） ###

*  这篇博客对于归并排序原理讲的特别好，我就不赘述了。

> [https://www.cnblogs.com/chengxiao/p/6194356.html][https_www.cnblogs.com_chengxiao_p_6194356.html]

*  动态过程图

> 出处（请多支持原创，我只是简单搬运）：[https://www.zhihu.com/search?type=content&q=堆排序][https_www.zhihu.com_search_type_content_q]  
> ![在这里插入图片描述][20190625125616965.gif]

#include <stdio.h>
    const int arrrlens = 8;
    int arr[arrrlens] = { 8, 7, 6 ,5 ,4 ,3 ,2 ,1 };
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Merge Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void Merge(int* arr, int left, int mid, int right)
    {
    	int p = left;
    	int q = mid + 1;
    	int t = 0;
    	/* 这块比较难理解点*/
    	while (p <= mid && q <= right)
    	{
    		if (arr[p] <= arr[q])
    			ans[t++] = arr[p++];
    		else
    			ans[t++] = arr[q++];
    	}
    	while (p <= mid)
    		ans[t++] = arr[p++];
    	while (q <= right)
    		ans[t++] = arr[q++];
    	t = 0;
    	while (left <= right)
    		arr[left++] = ans[t++];
    }
    /*Merge-Sort SourceCode*/
    void MergeSort(int* arr, int p, int r)
    {
    	if (p < r) //Termination conditions
    	{
    		int q = (p + r) / 2;
    		MergeSort(arr, p, q);
    		MergeSort(arr, q + 1, r);
    		Merge(arr, p, q, r);
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	int r = arrrlens - 1;
    	int p = 0;
    	MergeSort(arr, p, r);
    	PrintArray(arr);
    	return 0;
    }

### 3.堆排序算法（附C源码） ###

*  堆排序

#include <stdio.h>
    const int arrrlens = 8;
    int arr[arrrlens] = { 4, 6 ,8 ,5 ,9, 1, 10, 22};
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Heap Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void swap(int *a, int *b)
    {
    	int temp = *b;
    	*b = *a;
    	*a = temp;
    }
    void Max_heap(int* arr, int i, int lens)
    {
    	int left = 2 * i + 1;
    	int right = 2 * i + 2;
    	if (left <= lens && arr[i] < arr[left])
    	{
    		swap(&arr[i], &arr[left]);
    		Max_heap(arr, left, lens);
    	}
    	if (right <= lens && arr[i] < arr[right])
    	{
    		swap(&arr[i], &arr[right]);
    		Max_heap(arr, right, lens);
    	}
    }
    void CreateHeap(int* arr)
    {
    	//自底向上建堆
    	for (int j = arrrlens-1; j >= 0; j--)
    	{
    		int n = j / 2;
    		for (int i = n; i >= 0; i--)
    			Max_heap(arr, i, j);
    		swap(&arr[j], &arr[0]);
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	CreateHeap(arr);
    	PrintArray(arr);
    	return 0;
    }

### 4.快速排序算法（附C源码） ###

*  快速排序

#include <stdio.h>
    const int arrrlens = 8;
    int arr[arrrlens] = { 8, 4 ,5 ,7 ,1, 3, 6, 2};
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Quick Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void QuickSort(int* arr, int left, int right)
    {
    	if (left > right)
    		return;
    	int p = left;
    	int q = right;
    	int key = arr[left];
    	while (p != q)
    	{
    		for (; q > p && arr[q] >= key;)  
    			q--;
    		arr[p] = arr[q];
    		for (; p < q && arr[p] <= key;)  
    			p++;
    		arr[q] = arr[p];
    	}
    	//将基准数key放到位置p,保证o(n)空间复杂度。
    	arr[p] = key;
    	QuickSort(arr,left, p-1);
    	QuickSort(arr, p+1, right);
    	return;
    }
    int main()
    {
    	PrintArray(arr);
    	QuickSort(arr, 0, arrrlens-1);
    	PrintArray(arr);
    	return 0;
    }

### 5.冒泡排序算法（附C源码） ###

*  冒泡排序
 *  动态过程图

> 出处（请多支持原创，我只是简单搬运）：[https://www.zhihu.com/search?type=content&q=堆排序][https_www.zhihu.com_search_type_content_q]  
> ![在这里插入图片描述][201906251714538.gif]

#include <stdio.h>
    const int arrrlens = 8;
    int arr[arrrlens] = { 8, 4 ,5 ,7 ,1, 3, 6, 2};
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Quick Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void swap(int* a, int* b)
    {
    	int temp = *b;
    	*b = *a;
    	*a = temp;
    }
    void BubbleSort(int *arr)
    {
    	for (int i = 0; i < arrrlens; i++)
    	{
    		for (int j = 0; j < arrrlens-1-i; j++)
    		{
    			//由于是j+1和j比较，所以j的范围要-1
    			//减去i是因为每次会把子序列的最小值放到后面部分
    			//后面部分已经有序，不用再去比较
    			if (arr[j] > arr[j + 1])
    				swap(&arr[j],&arr[j+1]);
    		}
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	BubbleSort(arr);
    	PrintArray(arr);
    	return 0;
    }

### 6.选择排序算法（附C源码） ###

*  选择排序

#include <stdio.h>
    const int arrrlens = 8;
    int arr[arrrlens] = { 8, 4 ,5 ,7 ,1, 3, 6, 2};
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Quick Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void swap(int* a, int* b)
    {
    	int temp = *b;
    	*b = *a;
    	*a = temp;
    }
    void SelectionSort(int *arr)
    {
    	for (int i = 0; i < arrrlens; i++)
    	{
    		int index = i;
    		for (int j = i+1; j < arrrlens; j++)
    		{
    			if (arr[j] < arr[index])
    				index = j;
    		}
    		swap(&arr[i], &arr[index]);
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	SelectionSort(arr);
    	PrintArray(arr);
    	return 0;
    }

### 7.希尔排序算法（附C源码） ###

*  希尔排序

#include <stdio.h>
    const int arrrlens = 15;
    int arr[arrrlens] = { 99, 5, 69, 33, 56, 13, 22, 55, 77, 48, 12, 88, 2,69,99 };
    int ans[arrrlens] = { 0 };
    void PrintArray(int* arr)
    {
    	printf("Shell Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void ShellSort(int* arr)
    {
    	
    	int gap = arrrlens/2;
    	while (gap > 0)
    	{
    		printf("gap: %d \n", gap);
    		gap /= 2;
    		for(int j = 0; j < gap; j ++)
    		{ 
    			for(int i = j + gap; i < arrrlens; i += gap)
    			{
    				int key = arr[i];
    				int k = i - gap;
    				while ( k >= j && arr[k] > key)
    				{
    					arr[k + gap] = arr[k];
    					k -= gap;
    				}
    				arr[k + gap] = key;
    			}
    		}	
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	ShellSort(arr);
    	PrintArray(arr);
    	return 0;
    }

### 8.计数排序算法（附C源码） ###

*  计数排序

#include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    const int arrrlens = 15;
    int arr[arrrlens] = { 99, 5, 69, 33, 56, 13, 22, 55, 77, 48, 12, 88, 2, 69, 99 };
    int const max_int = 2147483647;
    int const min_int = -2147483647;
    void PrintArray(int* arr)
    {
    	printf("Shell Sort\n");
    	for (int ii = 0; ii < arrrlens; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    void CountingSort(int* arr)
    {
    	int max = min_int;
    	int min = max_int;
    	for (int ii = 0; ii < arrrlens; ii++)
    	{
    		if (max < arr[ii])
    			max = arr[ii];
    		if (min > arr[ii])
    			min = arr[ii];
    	}
    	const int COUNTINGARR_LENS = max - min+1;
    	int* CountingArr = (int*)calloc(COUNTINGARR_LENS, sizeof(int));
    	memset(CountingArr, 0, COUNTINGARR_LENS);
    	for (int ii = 0; ii < arrrlens; ii++)
    		CountingArr[arr[ii]-min] += 1;
    	for (int ii = 0; ii < COUNTINGARR_LENS; ii++)
    	{
    		for(int jj=0; jj < CountingArr[ii]; jj++)
    			printf("%d ", min+ii);
    	}
    }
    int main()
    {
    	PrintArray(arr);
    	CountingSort(arr);
    	return 0;
    }

### 9.基数排序算法（附C源码） ###

*  计数排序

#include <stdio.h>
    #include <stdlib.h>
    #include <memory.h>
    #include <math.h>
    const int arrrlens = 5;
    int arr[arrrlens] = { 2314, 5428, 373, 2222, 17 };
    int const max_int = 2147483647;
    int const min_int = -2147483647;
    void PrintArray(int* arr, int n)
    {
    	printf("Shell Sort\n");
    	for (int ii = 0; ii < n; ii++)
    		printf("%d ", arr[ii]);
    	printf("\n");
    }
    int MaxData(int* arr)
    {
    	int max = min_int;
    	for (int ii = 0; ii < arrrlens; ii++)
    	{
    		if (arr[ii] > max)
    			max = arr[ii];
    	}
    	int digit = 0;
    	while (max > 0)
    	{
    		max = max / 10;
    		digit++;
    	}
    	return digit;
    }
    void RadixSort(int* arr)
    {
    	int digit = MaxData(arr);
    	int base = 1;
    	//printf("%d ", digit);
    	while (digit--)
    	{
    		int count[10] = {0};
    		int temp[arrrlens] = {0};
    		for (int ii = 0; ii < arrrlens; ii++)
    		{
    			int num =  arr[ii] / base % 10;
    			count[num] ++;
    		}
    		for (int ii = 1; ii < 10; ii++)
    			count[ii] = count[ii] + count[ii - 1];
    		for (int ii= arrrlens-1; ii >= 0; ii--)
    		{
    			int num = arr[ii] / base % 10;
    			temp[--count[num]] = arr[ii];
    		}
    		for (int ii = 0; ii < arrrlens; ii++)
    			arr[ii] = temp[ii];
    		base *= 10;
    		PrintArray(arr,arrrlens);
    	}
    }
    int main()
    {
    	RadixSort(arr);
    	return 0;
    }

[InsertSort]: /images/20211228/d29d557ef91a48e5b516dc7d49d4d507.png
[https_www.zhihu.com_search_type_content_q]: https://www.zhihu.com/search?type=content&q=%E5%A0%86%E6%8E%92%E5%BA%8F
[20190625125455307.gif]: /images/20211228/4dad6505069c4ad1892ce0606bc4259a.png
[https_www.cnblogs.com_chengxiao_p_6194356.html]: https://www.cnblogs.com/chengxiao/p/6194356.html
[20190625125616965.gif]: /images/20211228/b861483d62a14816869670764fe23a9c.png
[201906251714538.gif]: /images/20211228/a0f4501641cd443da1b5bcb656d38061.png