【学习笔记】排序

选择排序

选择排序是一种简单的排序算法。它的原理是每次找到数组中的最小值放到正确的位置。
选择排序的最好、最坏、平均时间复杂度都是 \(O(n^2)\)，空间复杂度为 \(O(1)\)。由于存在交换这一操作，选择排序是一个不稳定的排序算法。

void selectionSort(int a[],int n){
	for(int i=1;i<n;i++){
		int minn=i;
		for(int j=i+1;j<=n;j++)
			if(a[j]<a[minn]) minn=j;
		swap(a[i],a[minn]);
	}
}

冒泡排序

冒泡排序是一种简单的排序算法。它的原理是交换相邻元素以消除所有逆序对。
冒泡排序的最好时间复杂度是 \(O(n)\)，在数组完全有序的情况下只需遍历一遍而不用交换。最坏时间复杂度和平均时间复杂度都是 \(O(n^2)\)，空间复杂度为 \(O(1)\)。由于存在交换这一操作，冒泡排序是一个不稳定的排序算法。

void bubbleSort(int a[],int n){ 
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=1;j<=n-i;j++)
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				flag=false;
			}
		if(flag) break;
	}
}

插入排序

插入排序是一种简单的排序算法。它的原理是从未排序的部分选择元素插入到已排序元素中正确的位置。
插入排序的最好时间复杂度是 \(O(n)\)，在数列相对有序的情况下效率高，而最坏时间复杂度和平均时间复杂度是 \(O(n^2)\)，空间复杂度是 \(O(1)\)。插入排序是稳定的排序算法。

void insertionSort(int a[],int n){
	for(int i=2;i<=n;i++){
		int j=i-1,tmp=a[i];
		while(j>=1&&a[j]>tmp){
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=tmp;
	}
}

希尔排序

希尔排序又称缩小增量排序，是插入排序的一种优化版本。希尔排序是一种不稳定的排序算法。
在进行希尔排序的时候，需要进行以下步骤：

1. 将数组分割成多个子序列，每个元素对应到数组里都相隔一个“增量”。
2. 对每个子序列进行插入排序。
3. 缩小增量，重复第一步，直到增量缩小为 1。
   由于插入排序在元素相对有序的情况下效率很高，所以希尔排序的效率相对也比较高。希尔排序的时间复杂度是算不出准确数值的。
   希尔排序的时间复杂度取决于它的增量。它的最好时间复杂度是 \(O(n)\)，即不用做任何操作。空间复杂度是 \(O(1)\)。

void shellSort(int a[],int n){
	for(int inc=n/2;inc>=1;inc>>=1)
		for(int i=inc;i<=n;i++){
			int key=a[i];
			int j=i;
			while(j>=inc&&key<a[j-inc]){
				a[j]=a[j-inc];
				j-=inc;
			}
			a[j]=key;
		}
}