C语言入门——排序

心已赠人 2023-06-07 08:17 48阅读 0赞

排序的方法有很多种比较常见的便为：冒泡排序、选择排序、插入排序、快速排序。

今天我们就围绕着四种排序来说，如果有兴趣的话可以去查找一下其他排序。

在排序这方面我们主要讨论：

*  **稳定**：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
 *  **不稳定**：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
 *  **时间复杂度**：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 *  **空间复杂度：**是指算法在计算机

## 一、冒泡排序 ##

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

***算法描述：***冒泡排序主要比较相邻元素之间大小，从第一个元素开始比较，将较大的元素不断向后移动，然后重复此操作，注意最后一个元素不需此操作。

***算法演示图：***

![20191013224101344.gif][]

***代码实现：***

void bulletSort(int arr[], int len)//冒泡排序
    {
    	int temp = 0;//作为交换的中间变量
    	for (int i = 0; i < (len - 1); i++)
    	{
    		for (int j = 0; j <( len-i-1); j++)
    		{
    			if (arr[j]>arr[j + 1])
    			{
    				temp = arr[j+1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    	}
    }

**二、选择排序**

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

***算法描述：***定义一个变量min，然后从数组中找到最小值赋值给min，然后交换a\[i\]与min的值。

***算法演示图：***

![20191013224119731.gif][]

void selectSort(int arr[], int len)
    {
    	int min;
    	int temp = 0;
    	for (int i = 0; i < len - 1; i++)
    	{
    		min = i;
    		for (int j = i + 1; j < len; j++)
    		{
    			if (arr[j]<arr[min])
    				min = j;
    		}
    		temp = arr[i];
    		arr[i] = arr[min];
    		arr[min] = temp;
    	}
    }

**三、插入排序**

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

***算法描述***：从第一个元素开发就已被标记，然后将后面一个作为交换元素，将如果后面一个元素小于前面一个元素的话，那么将元素不断的向左边移动。

***算法演示图：***

![20191013224133368.gif][]

***代码实现：***

void insertSort(int arr[], int len)
    {
    	int temp = 0;
    	int j = 0;
    	for (int i = 1; i < len; i++)
    	{
    		j = i - 1;
    		temp = arr[i];
    		while(j >= 0 && arr[j]>temp)
    		{
    			arr[j+1] = arr[j];
    			j--;
    		}
    		arr[j + 1] = temp;
    	}
    }

***四快速排序：***

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

***算法描述：***前面的三种排序相对于简单，后面这一种快速排序就得浪费点脑力了，快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

***算法演示图：***

![20191013224143343.gif][]

***代码实现：***

void quickSort(int arr[], int left, int right)
    {
    	if (left >= right)return;
    	int i = left, j = right, temp;
    	while (i < j)
    	{
    		while (i < j&&arr[left] < arr[j])
    			j--;
    		while (i<j&&arr[left]>=arr[i])
    			i++;
    		if (i < j)
    		{
    			temp = arr[i];
    			arr[i] = arr[j];
    			arr[j] = temp;
    		}
    	}
    	//跳出循环则说明i==j
    	temp = arr[left];
    	arr[left] = arr[i];
    	arr[i] = temp;
    	quickSort(arr, left, i - 1);
    	quickSort(arr, i+1, right);
    }

如果大家想了解更多C语言知识的话可以关注我，或者来加入我们的公众号：C语言进阶之旅  希望各位都能收获到更多的C语言知识，在编程这条道路上越走越远！！！

[20191013224101344.gif]: /images/20230601/04b59d81bfb54d3686a5fa2634df8187.png
[20191013224119731.gif]: /images/20230601/8f4a398bf68f408d9ab2676c0045975f.png
[20191013224133368.gif]: /images/20230601/7e8931642415488da5a4d505fe252633.png
[20191013224143343.gif]: /images/20230601/79f5ae4059aa4ac28c3a105d6f0eef5e.png