八大排序

排序算法总结

排序算法	平均时间复杂度
冒泡排序	O(n2)
选择排序	O(n2)
插入排序	O(n2)
希尔排序	O(n1.5)
快速排序	O(N*logN)
归并排序	O(N*logN)
堆排序	O(N*logN)
基数排序	O(d(n+r))

 

 

三. 插入排序(Insertion Sort)

---

1. 基本思想：
   在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

2. 过程：

   

   插入排序

   

   相同的场景

3. 平均时间复杂度：O(n2)

4. C代码实现：

#include <stdio.h>
 
void InsertSort(int array[], int len)
{	
    for (int i = 0; i < len; i++) {
			//内层循环就从i的前一个到0（因为i的前一个是已经排好序的【第一个的前一个就不用管了】，所以，我们的第i个要跟前i-1个逐一比较交换，直到位置合适[看下面]）
			for (int j = i -1; j >= 0; j--) {
				//如果前面的大于后面就交换，这样才会升序排列嘛
				if (array[j] > array[j+1] ) {
					int temp; 
					temp=array[j];
					array[j]=array[j+1];
					array[j+1]=temp;
				}else{//否则说明已经在正确的位置上了，退出内层循环，继续插入下一个元素
					break;
				}
			}
		}
}
 
int main()
{
    int i = 0;
    int a[] = {8, 2, 5, 3, 6, 7, 1, 9, 0};
    int length = sizeof(a) / sizeof(a[0]);
    InsertSort(a, length);
    for(i = 0; i < length; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}