经典排序算法——快排和插入排序

大厂面试的时候经常会问到一些的算法题，前段时间就被要求手写一段快排算法。虽然这些上学的时候有学过，可平时关注的也少，而且很多人都有这种感觉，代码一看就懂，当时以为自己掌握了，可过段时间让自己来写就忘了。
其实归根到底还是没有理解算法的真正思想，只是单纯的跟着别人的思路走，知其然不知所以然，时间一久自然就忘了。

快速排序

快速排序属于拿着元素找位置的算法。思路非常简单明了，首先给第一个元素找到它正确的位置并把它放置其中，此时该元素将原数组分为两半，左半边的元素都小于或等于它，右半边的元素都大于它，对这两个子数组重复刚才的操作，直到子数组中只有一个元素，此时排序完成。

/**
 * @param s
 * @param i 左边界
 * @param j 右边界
 */
public static void quickSort(int[] s, int i, int j) {
    if (i < j) {
        int left = i, right = j, inser = s[i];
        while (left < right) {
            while (left < right && inser < s[right])
                right--;//缩小右边界
            if (left < right) s[left++] = s[right];//缩小左边界

            while (left < right && inser > s[left]) left++;
            if (left < right) s[right--] = s[left];
        }
        s[left] = inser;

        quickSort(s, i, left - 1);
        quickSort(s, left + 1, j);
    }

}

直接插入排序

插入排序的思想，先给定一个排好序的序列，再让后续的值与前面已排好序的值依次比较，如果小于前面的值就插入在前列，一直这样循环的操作后续的值。比如把第一个元素作为有序的值，第二个元素和第一个元素比较，根据比较结果，排序两者的位置使之有序，第三个元素和前两个元素比较，根据排序结果使之有序，直到第N个元素完成排序。

  public static void insetSort(int[] data) {
    for (int i = 1; i < data.length ; i++) {
        int temp = data[i];//从第二个元素开始
        int j = i - 1;

        while (j >= 0 && temp < data[j]) {
            //将data[j]后移
            data[j + 1] = data[j];
            //j的位置前移
            j--;
        }
        data[j + 1] = temp;// 将temp插入到正确的位置
    }
}