经典排序算法(一)

算法相关概念：

1.稳定性

如果a原本在b的前面，而a=b，排序之后a仍然在b的前面，则算法为稳定，否则为不稳定。即排序算法是否改变相同元素的初始顺序。

2.时间复杂度

一个算法的执行时间，去掉不定因素（如计算机的运行能力），算法的执行时间其实是受算法的输入和算法本身影响的，所以我们衡量一个算法的执行时间，可以通过基本运算的执行次数来衡量。通常，用T（N）表示基本运算的执行次数。而什么叫做基本运算？加、减、乘、除、比较等都是基本的运算。

3.空间复杂度

指算法在计算机内执行时所需储存空间的度量，他也是数据规模N的函数。

4.大O符号（渐进上界）

设f和g是定义域为自然数集N上的函数，若存在正数c和n₀，使得对一切n>=n₀有cg(n)>=f(n)>=0成立，则成f(n)的渐近线上界是g(n)，记做：f(n)=O(g(n)). g(n)称为f(n)的渐进上界。

5.常数时间(空间)

用O(1)表示，表示时间复杂度（空间复杂度）与输入N无关。

1.冒泡排序(Bubble Sort)

算法思想：

对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把较大的元素移动到数组后面（交换两个元素的数值），这样一来，较小的元素就像气泡从底部上升到顶部，故称为冒泡排序。

算法步骤：

1.比较相邻的元素，如果后者比前者大交换两者，从第一对到最后一对，第一次循环结束后最大的元素出现在队尾，待排序数组长度减一。

2.对待排序数组重复1中操作，其中每次循环结束完成1个元素的排序（排出当前数组最大的元素至队尾，第一次循环最大的元素，第二次循环次大的元素…）

3.重复1，2中操作直至数组排序完成

代码实现(java)

	public static void sort(int[] arr){
      //外层循环控制比较趟数，最后趟将两个数排好，总共需要排length-1趟
        for(int i=0;i<arr.length-1;++i)
             /*内层循环控制每趟比较的比较次数，因每趟比较使最大的数排至数列尾,
             所以每趟比较次数为arr.length-1-i*/
   			 for(int j=0;j<arr.length-1-i;++j)
             	//如果后者比前者小就交换位置(大数向后移动，小数向前移动)
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }

说明：冒泡排序由双层循环实现，外层循环控制排序的趟数，排序的趟数为数组长度-1次，因为最后一轮循环只剩下一个数组元素，不需要继续排序，数组已经排序完成。内层循环比较两个邻近元素的大小，已确定是否需要交换位置，对比的次数随排序的趟数递减，这是因为每趟排序均使当前第i大的元素放置数组尾的适当位置。

算法可视化：

图片来自于：https://www.cnblogs.com/onepixel/articles/7674659.html

算法复杂度

时间复杂度：

最坏:逆序数组，需要比较1+2+…+n-1=(n²-n)/2次，交换（n²-n）/2次，故时间复杂度为O(n²)

最好:顺序数组，所有元素从小到大一次排序，需要（n²-n)/2次比较，时间复杂度为O(n²)。

(可以对冒泡排序算法进行改进，设置一个flag值，如果内层循环没有进行交换则说明此时数组已经有序，跳出循环即可，最好情况为O(n))

	for (int i = 0; i < arr.length - 1; ++i) {
		// 定义一个flag变量
		boolean flag = false;
		for (int j = 0; j < arr.length - 1 - i; ++j) {
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				flag = true;
			}
		}
		// 如果flag为flase说明内层没有交换，此时数组已有序，排序完成，跳出外层循环
		if (!flag)
			break;
	}

平均：O(n²)

空间复杂度：O(1)

稳定性：稳定

2.插入排序(Insertion Sort)

算法思想：

像整理桥牌一样，将每一张牌插入到其他已经有序的牌中的适当位置。起始索引为1，索引左边的所有元素是有序的（第一个元素默认有序），索引右侧是待排序数组，将索引处的元素插入到有序序列中适当的位置，这样每次循环，索引右移一位，有序序列长度加一，待排序数组长度减一，直到最后一个元素排序，数组的排序就完成了。

算法步骤：

1.第一个元素默认已排序，取下一个元素，记录待插入元素值，在已排序的元素中从后至前进行扫描并依次与待插入元素进行比较。

2.如果已排序的元素值大于待插入元素值，则说明待插入元素值应该插入在此元素值前面，将此元素值向后移一位，继续向前查找，直到找到一个小于待插入元素或者数组索引小于等于0（此时说明待插入元素比已排序数组任何值都小），将待插入元素插入到正确位置。

3.重复1，2中步骤，直到数组所有元素完成排序。

代码实现(Java)

	public static void sort(int[] arr) {
		int currentValue = 0;
		// 外层循环控制循环次数，第一个元素默认有序，
		// 待排序的数组下标从1开始，到最后一个元素length-1结束
		for (int i = 1; i < arr.length; ++i) {
			currentValue = arr[i];
			int index = i;
			// 在已排序数组中找小于待排序元素时或者已排序数组都大于待排序元素时终止内层循环
			while (arr[index - 1] > currentValue && index - 1 >= 0) {
				// 将此元素向后移一位
				arr[index] = arr[index - 1];
				index--;
			}
			arr[index] = currentValue;
		}
	}

算法可视化：

图片来自于：https://www.cnblogs.com/onepixel/articles/7674659.html

算法复杂度：

时间复杂度：

最好：有序数组，length-1次比较，时间复杂度为O(N)

最坏:逆序数组，外层循环循环length-1次，内层循环循环length-1-1次，时间复杂度为O(N²)

平均：O(N²)

注：插入排序需要交换操作和数组中倒置的数量相同，需要比较的次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一。

空间复杂度:O(1)

稳定性：稳定

适用情况：插入排序所需要的时间取决于数组中元素的初始顺序，对于部分有序或者接近有序的数组用插入排序会比随机数组或逆序数组快。插入排序也适合小规模数组。

3.选择排序(Selection Sort)

算法思想：

每次循环在未排序的序列中找出最小（大）的元素，将其存放于已排序序列的末尾，这样第一次循环结束找到了最小（大）的元素，第二次循环周到了次小（大）的元素，重复循环，直到所有序列均已排序。

算法步骤：

1.在数组中找出最小值，将其与数组第一个元素交换位置，这样就排好了第一个元素，未排序数组的大小减小一.

2.按照1中排序方法，找到未排序数组中的最小值，并将其与数组第二个元素交换位置，这样第二小的元素就排好，未排序为数组大小减小一。

3.重复2中的步骤，直到剩下的数组排序完成。其中长度为N的数组需经过N-1次循环完成排序。

代码实现(Java)

	public static void sort(int[] arr) {
		// 外层循环i代表未排序数组的第一个元素，从0到length-1-1，循环length-1次
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			// 内层元素从i+1开始直到最后一个元素length-1
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			// 循环完毕交换索引为i和minIndex的值
			int temp;
			temp = arr[i];
			arr[i] = arr[minIndex];
			arr[minIndex] = temp;
		}
	}

可视化：

图片来自于：https://www.cnblogs.com/onepixel/articles/7674659.html

算法复杂度：

时间复杂度：

最好：有序数组，比较(N²-N)/2次，交换N-1次，T(N)=O(N²)

最坏：比较(N²-N)/2次，交换N-1次，T(N)=O(N²)

平均：T(N)=O(N²)

空间复杂度:O(1)

稳定性:稳定

适用情况：

选择排序的运行时间与输入无关，因为每次排序选择排序都会找到待排序数组中最小的元素，所以选择排序的数据移动是最少的。

4.希尔排序（Shell Sort）

算法思想：

是改进版的插入排序，将待排序的数组元素按下标的一定增量分组，分成多个子序列，分别对各个子序列进行插入排序算法排序，然后依次缩减增量再进行排序，直到增量为1时，进行最后一次插入排序，希尔排序完成。

基本步骤：

1.首先选择增量gap=N/2，按照增量序列的个数K，对数组进行K次插入排序。

2.减小增量为gap=N/2/2，按照增量序列的个数K，对数组K次插入排序。

3.重复2步骤进一步减小增量，直到增量gap=1时，按照增量序列的个数（此时整个数组即为增量序列）对数组进行最后一次插入排序，希尔排序完成。

代码实现(Java)

public static void sort(int[] arr) {
	// 外层循环控制增量
	for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {

		for (int i = gap; i < arr.length; i++) {
			// 插入排序
			int currentValue = arr[i];
			int index = i;
			while (index - gap >= 0 && arr[index - gap] > currentValue) {
				arr[index] = arr[index - gap];
				index -= gap;
			}
			arr[index] = currentValue;
		}
	}
}

算法过程可视化：

图来自于https://www.cnblogs.com/chengxiao/p/6104371.html

算法复杂度：

时间复杂度：(希尔排序的时间复杂度与选中的增量d有关)

最好：O(N^1.3)

最坏：O(N²)

空间复杂度：O(1)

稳定性：不稳定。

希尔排序中相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。

适用情况：

与插入排序不同，希尔排序可以用于大型数组，并且对于任意排序的数组表现很好。

-----------------------------------------------------------------------------------------------------------------------参考资料：
https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.cnblogs.com/chengxiao/p/6104371.html

算法（第四版）人民邮电出版社

( 注：部分资料参考网络，如有侵权或错误请在留言与我联系，欢迎关注我的微信公众号“搬砖小张”，一起学习，一起进步)