常见数据结构与算法

面试题

排序算法

直接插入排序

直接插入排序的基本思想是：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素个数从只有一个数据元素开始逐次增大，当子集合大小最终与集合大小相同时排序完毕。

算法复杂度：$n^2$

private static int[] sorts = {6,1,8,5,10,6,31,14};
public static void main(String[] args) throws Exception {
    InsertSort();
}
/**
 * 1.记录当前排序元素。
 * 2. 依次和之前元素比较，大数后移。小数over
 */
public static void InsertSort() {
    System.out.println("排序前：" + JSONObject.toJSONString(sorts));
    for(int i = 0 ; i < sorts.length -1 ; i++) { // 第几次比较
        int j = i ;
        int key = sorts[i+1];
        while (j > -1 && key < sorts[j] ) { // 倒退计数
            sorts[j+1] = sorts[j];
            j-- ;
        }
        sorts[j+1] = key ;
    }
    System.out.println("排序后:" + JSONObject.toJSONString(sorts));
}

冒泡排序

从左往右，依次比较，大数后移。 小的往上冒，大的往下沉！

算法复杂度：$n^2$

public static void bubbleSort() {
    System.out.println("排序前：" + JSONObject.toJSONString(sorts));
    int flag = 1 ;
    int temp = 0 ;
    for(int i = 1 ; i < sorts.length && flag == 1; i++) { //i 表示第几轮冒泡
        flag = 0 ;
        for(int j = 0 ; j < sorts.length - i ; j++) {
            if(sorts[j] > sorts[j+1]) {
                flag = 1 ;
                temp = sorts[j];
                sorts[j] = sorts[j+1];
                sorts[j+1] = temp ;
            }
        }
    }
    System.out.println("排序后：" + JSONObject.toJSONString(sorts));
}

快速排序

快速排序算法的基本思想是：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素（通常取a[low]）作为标准，调整数组a中各个元素的位置，使排在标准元素前面元素的关键字均小于标准元素的关键字，排在标准元素后面元素的关键字均大于或等于标准元素的关键字。

这样一次过程后，一方面将标准元素放在了未来排好序的数组中该标准元素应在的位置上，另一方面将数组中的元素以标准元素为中心分成了两个子数组，位于标准元素左边子数组中元素的关键字均小于标准元素的关键字，位于标准元素右边子数组中元素的关键字均大于等于标准元素的关键字。然后对这两个数组中的元素分别再进行方法类同的递归快速排序。递归算法的出口条件是high > low。

详细参见博文：快速排序——JAVA实现（图文并茂）

最好情况下快速排序算法的空间复杂度为O($log2^n$)，最坏情况下快速排序算法的空间复杂度为O(n)，平均空间复杂度为O($log2^n$)

快速排序算法是一种不稳定的排序方法。

二分查找

有序顺序表上二分查找算法的基本思想是：在一个查找区间中，确定出查找区间的中心位置，用待查找数据元素的关键字与中心位置上的数据元素的关键字比较，若两者相等，则查找成功；否则，若前者小于后者，则把查找区间定为原查找区间的前半段继续这样的过程；否则，则把查找区间的后半段继续这样的过程。

算法复杂度：$logz^n$

  static int[] findNum = {1,2,3,5,6,8,10,15,19};
    static int find = 15 ;
    public static void main(String[] args) {
        System.out.println(binarySearch());
    }
    public static int binarySearch() {
        int low = 0 ;
        int high = findNum.length -1 ;
        int mid = 0 ;
        while (low < high) {
            mid = (low + high) / 2 ;
            if(find == findNum[mid]){
                return mid;
            } else if(find < findNum[mid]) {
                high = mid - 1 ;
            }  else if(find > findNum[mid]) {
                low = mid + 1 ;
            }
        }
        return -1 ;
    }