目录

一.直接插入排序

二.希尔排序

三.冒泡排序

四.快速排序

---

一.直接插入排序

1.算法思路：

顾名思义，就是将一个新的元素插入已经排好的序列中。

比如一个待排的序列：49,38,65,97,76,13,27,49，用数组a[1…n]表示，升序排序如图所示，其中（）表示已经排好的元素。

为了在查找插入位置的过程中避免数组下标出界，在a[0]处设置一个哨兵。比如在插入a[i]的过程中，如果a[i]小于a[i-1],先将a[i]放在哨兵a[0]的位置，在从后往前比较的过程中，如果a[0]<a[j]就就将a[j]后移一个单位，直到找到插入的位置，再将a[0]还原到正确的插入位置。直接插入排序算法的时间复杂度为O(n^2)，并且是一种稳定的排序方法。

2代码：

for (int i = 1; i <= n; i++) { if(a[i] < a[i-1]){ //如果a[i] < a[i-1]就进行插入，否则不管 a[0] = a[i]; //把待插入的元素放入哨兵 a[i] = a[i-1]; //a[i-1]后移 int j = i-2; while(a[j] > a[0]){ a[j+1] = a[j]; //逐个后移，直到找到插入的位置 j--; } a[j+1] = a[0]; //把a[0]还原到插入的位置 } }

 

二.希尔排序

1.算法思路：

希尔排序是插入排序的一种，是采用了分组插入的方式，先将整个带排序的数组分割成几组，减少排序的数量，对每组进行直接插入排序。然后增加每组的数据量，重新分组。当几次分组排序过后，整个序列已基本有序，再进行一次全体的直接插入排序。希尔对记录的分组，不是简单地 ”逐段分割＂， 而是将相隔某个 “增量” 的记录分成一组。

1.第一趟取增量 d1 (d1<n) 把全部记录分成小个组，所有间隔为 di 的记录分在同一组，在各个组中进行直接插入排序。

2.第二趟取增量 d2 (d2<d1), 重复上述的分组和排序。

3.依次类推， 直到所取的增量 d1 = 1 (d1 <dt-1 <…< d2 < d,), 所有记录在同一组中进行直接插入排序为止。

2.代码：

int[] a = {49,38,65,97,76,13,27,49,55,4}; int n = a.length; int key; //临时存储，类似于直接插入的哨兵 for (int d = n/2;d > 0;d/=2) { //增量,从n/2开始每次除2，直到d=1 for (int i = d; i < n; i++) { //i从d开始，因为第一个只有一个元素不用管。 key = a[i]; int j = i-d; while(j>=0 && key < a[j]){ a[j+d] = a[j]; //后移 j-=d; } a[j+d] = key; } }

三.冒泡排序

1.算法思路:

冒泡排序比较简单。冒泡排序是每次比较相邻的两个元素，把较大移到后面，经过一轮交换后，前n个元素的最大值就到了最后，再对前n-1个元素进行同样的办法，就可以把前n-1个中最大的元素移到倒数第二的位置上。重复以上步骤就可以完成排序。

2.代码：

for (int i = 0; i < a.length-1; i++) { //i表示比较的数趟 for (int j = 0; j < a.length-i-1; j++) { //第0趟比较n个元素，第1趟比较n-1个元素··· if(a[j] > a[j+1]){ //把较大的，移到后面 int t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } }

四.快速排序

1.算法思路：

快速排序和冒泡排序都属于交换排序。快速排序的基本思想是分治排序，先随便找一个基准值，把数组中所有小于它的值放到基准值的左边，把大于它的值放到基准值的右边。然后左右两边的数组再进行独立的排序，对于左边的数组也同样随便找一个基准值，重复上面的步骤，右边也一样。可以看出这是一个递归的调用。时间复杂度为O(nlgn),是不稳定的排序算法。

图解：

一般选第一个元素作为基准值，然后用两个指针i，j分别指向数组的头和尾部

首先移动j，找到一个比基准值小的元素之后，不动，然后移动i，找到比基准值大的元素后，交换两个指针指向的值

当i和j指向同一个位置的适合，就找到了基准值的位置，就把基准值和这个位置得到元素交换。

最后再分别对左右两边重复上面的步骤，直到 j<i 终止。

2.代码：

void QuickSort( int i, int j) { if(j<i) return;//结束条件 int key = a[i];//基准值 int e = i;//记录最前面位置 int l = j;//记录最后面位置 while(i!=j){ while(a[j] >= key && i < j) j--; while(a[i] <= key && i < j) i++; //找到了两个待交换的值，并且i和j不重合 if(i < j){ int t = a[i]; a[i] = a[j]; a[j] = t; } } //基准值和中间那个数交换 a[e] = a[i]; a[i] = key; QuickSort(e,i-1);//递归基准值左边部分 QuickSort(i+1,l);//递归基准值右边边部分 }