数据结构与算法——排序算法1

这段时间在复习数据结构与算法,准备花点时间好好捋一捋基础

在日常的项目中，排序算法可以说是程序员的基础了。而且面试中也有较大几率被问到，下面让我们回顾一下几个基础的排序算法。

选择排序

选择排序时间复杂度为O(n^2),大致思想就是每次选择最小的元素将其放在数组的前端，然后不停的迭代就行，由于比较简单，也不多说。简单的看一下演示图，和我的代码实现

SelectionSort.gif

由于大部分排序都要交换数组中元素的位置，所以写一个swap（）函数

private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

下面就是排序算法了

public static void sort(Comparable[] arr) {
  int len = arr.length;
  for (int i = 0; i < len; i ++) {
    int minIndex = i;
    for (int j = i  + 1; j < len; j ++) {
      if (arr[j].compareTo(arr[minIndex])) 
        minIndex = j;
    } 
    swap(arr,i, minIndex);
  }
}

插入排序

插入排序时间复杂度同样为O(n^2)，思路与选择排序类似，就是每次与之前一个元素进行比较，如果比前面那个元素小，就插入那个元素前面

InsertionSort.gif

 public static void sort(Comparable[] arr){
        int len= arr.length;
        for (int i = 0; i < len; i++) {
            Comparable t= arr[i];
            int j = i;
            for( ; j > 0 && arr[j-1].compareTo(t) > 0 ; j--)
                arr[j] = arr[j-1];
            arr[j] = t;
        }
    }

冒泡排序

冒泡排序可以说是我会的第一个排序算法了，实现起来也很简单，就是将大的元素不断的冒泡，到数组的最后面

BubbleSort.png

public static void sort(Comparable[] arr){
        int len = arr.length;
        for (int i = len - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

希尔排序

希尔排序实质上是分组插入排序，先取一定的增量将数组分割成若干个序列进行插入排序，然后再缩小增量进行排序，直到增量为1（PS： 不知道为什么我写的这个希尔排序效率非常低，数据比较多的时候，比其他算法都要慢上不少，过几日我要改进一下）

image.png

public static void sort(Comparable[] arr) {
        int len = arr.length;
        int d = len / 2;
        while (d >= 1) {
            for (int i = 0; i < arr.length; i++){
                for (int j = i; j < arr.length - d; j += d) {
                    if (arr[i].compareTo(arr[j + d]) > 0) {
                        swap(arr, j , j+d);
                    }
                }
            }
            d = d /2;
        }
    }

---

上面都是些比较简单的算法，明后天将为大家带来快速排序和双路快排和三路快排，分析一下快速排序有时效率较低的原因