基础排序算法

选择排序

假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么选择排序的排序流程为：

1. 在这个数组中找出最小值与第一个元素交换，现在数组为[0,1,3,2,8,4,2]

2. 在这个数组中除了第一个位置的元素外找出最小值与第二个元素交换，因为第二个元素就是最小的所以此次没有发生变化。现在数组为[0,1,3,2,8,4,2]

3. 在这个数组中除了第一个、第二个位置的元素外找出最小值与第三个元素交换，现在数组为[0,1,2,3,8,4,2]

4. 在这个数组中除了第一个、第二个、第三个位置的元素外找出最小值与第四个元素交换，现在数组为[0,1,2,2,8,4,3]

5. 在这个数组中除了第一个、第二个、第三个、第四个位置的元素外找出最小值与第五个元素交换，现在数组为[0,1,2,2,3,4,8]

6. 在这个数组中除了第一个、第二个、第三个、第四个、第五个位置的元素外找出最小值与第六个个元素交换，因为第六个元素就是最小的所以此次没有发生变化。现在数组为[0,1,2,2,3,4,8]

现在整个数组是不是已经变得有序了呢。接下来我们看图解版本

接下来上代码

int i;        // 有序区的末尾位置
int j;        // 无序区的起始位置
int min;    // 无序区中最小元素位置
int []a=new int[]{3,1,0,2,8,4,2};

for(i=0,n=a.length; i<n; i++) {
    min=i;
    // 找出"a[i+1] ... a[n]"之间的最小元素，并赋值给min。
    for(j=i+1; j<n; j++) {
        if(a[j] < a[min])
            min=j;
    }

    // 若min!=i，则交换 a[i] 和 a[min]。
    // 交换之后，保证了a[0] ... a[i] 之间的元素是有序的。
    if(min != i) {
        int tmp = a[i];
        a[i] = a[min];
        a[min] = tmp;
    }
}

2

◆

插入排序

◆

相信大家都有打扑克的经历，那么我们今天的插入排序就以拿牌为例开始讲（注意只是举例，不是按打牌的规则哦）

1. 我们拿到了一张牌3，我们把它放手里，现在手里有牌[3]

2. 我们拿到了一张牌1，拿它与手里最后一张牌也就是3比较，发现1比3小，所以我们把它插入到3的前面，现在手里有牌[1,3]

3. 我们拿到了一张牌0，拿它与手里最后一张牌也就是3比较，发现0比3小，所以我们把它插入到3的前面，接着与3的上一张比较发现0比1还小，那么就把0在插入到1的前面，现在手里有牌[0,1,3]

4. 我们拿到了一张牌2，拿它与手里最后一张牌也就是3比较，发现2比3小，所以我们把它插入到3的前面，接着与3的上一张比较发现2比1大，那么就不需要动了，现在手里有牌[0,1,2,3]

5. 我们拿到了一张牌8，拿它与手里最后一张牌也就是3比较，8比3大，那么就不需要动了，现在手里有牌[0,1,2,3,8]

6. 。。。

现在你明白什么叫做插入排序了么？如果你不明白的话也没关系，我还专门画了一张图：

接下来上代码

int []num=new int[]{3,1,0,2,8,4,2};
for (int i=1,n=num.length;i<n;i++){
    if(num[i]<num[i-1]){
        for (int j=i;j>0;j--){
            if(num[j]<num[j-1]){
                int temp=num[j];
                num[j]=num[j-1];
                num[j-1]=temp;
            }
        }
    }
}
for (int i:num){
    System.out.print(i+",");
}

3

◆

快速排序

◆

快速排序是一个运用了分治法和递归算法的排序方式。假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么在进行快速排序的时候我们先要进行一些准备：

* n作为一个数组中的标杆，一趟排序过后我们要把数组中所有大于n的数放在它的右边，所有小于n的放在它的左边。一般情况下我们会取数组第一个元素作为n，在此数组中就是n=3

* i我们使用i来找数组中大于标杆的值，i初始指向数组第一个位置

* j我们使用j来找数组中小于标杆的值，j初始指向数组最后一个位置

下面开始排序：

1. 先从数组右边开始，我们发现j指向的元素2比标杆n小，那么我们将j指向的元素赋值给i指向的元素，停止操作。此时数组为[2,1,0,2,8,4,2]，i指向第一个位置，j仍指向最后一个。

2. 从数组左边开始，i指向的元素2比标杆小，所以不做操作，使i++，i指向的元素1比标杆小，所以不做操作，使i++，一直到i指向8的时候比标杆大（注意此处如果等于的话也要操作），那么就把i指向的元素赋值给j指向的元素，此时数组为[2,1,0,2,8,4,8]，i指向第五个位置。也就是元素8，j仍然指向最后一个位置。

3. 继续从右边操作，j指向的8不比n小，所以不做操作，j–，4不比3小，不做操作，j–。现在i和j的位置重合了，把n放到这个位置上。我们此轮的操作也就结束了

4. 接下来我们把3所在的位置左边分为一个数组，右边位置分为一个数组再次进行刚才的操作。（此处就是一个递归调用了）

接下来就来看一个图片描述的过程

接下来上代码

public static void quickSort(int[] a, int l, int r) {
    if (l < r) {
        int i,j,n;
        i = l;
        j = r;
        n = a[i];
        while (i < j) {
            while(i < j ){
                if(a[j] < n){
                    a[i] = a[j];
                    break;
                }
                j--;
            }
            while(i < j ){
                if(a[i] >= n){
                    a[j] = a[i];
                    break;
                }
                i++;
            }
        }
        a[i] = n;
        quickSort(a, l, i-1); /* 递归调用 */
        quickSort(a, i+1, r); /* 递归调用 */
    }
}

4

◆

希尔排序

◆

希尔排序呢，其实可以理解为插入算法排序的一个升级版了.

回忆一下当使用插入排序在进行排序数据量非常大的数据时，有一个很小的数据出现在了数组的最后，那么我们就要移动了这个数据前面所有的元素给它放置到合适的元素。例如：我们要排序的数组为[1,2,3,4,5,6,7，。。。此处省略一百万。。.,0]

相信大家肯定不喜欢这个0往前移动一百万此吧，希尔排序的出现其实就是为了解决这个问题的

希尔排序使用了分治算法，先把整个大的数组根据某个增量分为若干个组，先对这若干个组进行一个调整，保证大部分小的数据会被调整到前面来。到最后再次进行插入排序，这样就大大加快了效率了。

来一个例子，如图所示，我们要排序的数组为[3, 1, 0, 2, 8, 4, 2,6,9,1,3,-2,8]

• 上方图片所说的增量就是我们进行分组的依据了。我们在这里初始值取得是数组得2分之一（此值没有标准的定义，只需保证大于1且小于数组长度即可），而红线所指向得就是我们根据这个增量所分的组了，我们分别针对每组进行排序。
• 可以在增量为3的结果种看到，第一组3，2，8 变为了2，3，8、第二组第三组没变、第四组变为了1，2、第五组变为了3，8、第六组变为了-2，4.
• 接下来增量减半，我们的数组分为3组，分别进行排序。
• 现在增量值经过再次减半后已经变为1了，我们可以通过观察数组发现，在数组的后面基本不可能出现最小的数据了，现在对数组进行插入排序的效率已经非常高了

不知道现在的你明白希尔排序了么？来看一看代码吧

void shellSort(int list[], int length){
  int gap,i,j,temp;
     for (gap = length/2; gap > 0; gap /= 2){
        for(i = gap; i < length; i++){
            for(j = i-gap; j>=0 && list[j]>list[j+gap]; j -= gap){
              temp = list[j];
                list[j] = list[j+gap];
                list[j+gap] = temp;
          }
       }
    }
}

5

◆

冒泡排序

◆

冒泡排序在排序算法中效率算最慢的一类了，但是因为它简单的缘故仍然是工作1-3年的程序员面试经常会碰到的算法问题。

假如我们现在要排序的数组为[3,1,0,2,8,4,2]

1. 第一轮排序为比较3和1，发现3比1大，那么我们就交换3和1，数组变成了[1,3,0,2,8,4,2]

2. 比较3和0，发现3比0大，那么我们就交换3和0，数组变成了[1,0,3,2,8,4,2]

3. 比较3和2，发现3比2大，那么我们就交换3和2，数组变成了[1,0,2,3,8,4,2]

4. 比较3和8，发现3没有8大，那么不操作，数组还是[1,0,2,3,8,4,2]

5. 比较8和4，发现8比4大，那么我们就交换8和4，数组变成了[1,0,2,3,4,8,2]

6. 比较8和2，发现8比2大，那么我们就交换8和2，数组变成了[1,0,2,3,4,2,8]

7. 现在第一轮的排序已经完成了，我们就筛选出来了最大值8，此时数字8已经在数组最后的位置了，下一轮排序我们就可以排除它了。第二轮排序为：比较1和0，发现1比0大，那么我们就交换1和0，数组变成了[0,1,2,3,4,2,8]

8. 比较1和2，发现1没有2大，那么不操作，数组还是[0,1,2,3,4,2,8]

9. 比较2和3，发现2没有3大，那么不操作，数组还是[0,1,2,3,4,2,8]

10. 比较3和4，发现3没有4大，那么不操作，数组还是[0,1,2,3,4,2,8]

11. 比较4和2，发现4比2大，那么我们就交换4和2，数组变成了[0,1,2,3,2,4,8]

12. 现在第二轮排序完成了，数组最后的4和8是不是已经有序了呢

聪明的你是不是已经发现了冒泡排序的规律了呢，代码实现：

int []a=new int[]{3,1,0,2,8,4,2};
int i,j;
int flag;                 // 标记
for (i=a.length-1; i>0; i--) {
    flag = 0;            // 初始化标记为0
    // 将a[0...i]中最大的数据放在末尾
    for (j=0; j<i; j++) {
        if (a[j] > a[j+1]) {
            // 交换a[j]和a[j+1]
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = 1;    // 若发生交换，则设标记为1
        }
    }

    if (flag==0)
        break;            // 若没发生交换，则说明数列已有序。
}
for (int ii:a){
    System.out.print(ii+",");
}