正文

学习数据结构的重要性

程序＝数据结构 + 算法，算法很重要，数据结构也很重要，只有掌握了这两者，我们才等于掌握了写程序的本领，才是合格的程序员哦。

算法复杂度比较

在网上看到的一篇总结，这个要背的。

数据结构重点：排序算法比较

这是我学数据结构的时候做的一个总结：

为什么要综合比较

见下图，这是一道排序算法的面试题（要求：稳定，快速），我在做这道题的时候，根据我总结的内容，很快便锁定了算法，首先，算法要求一个稳定，快速的算法，我们便可以确定要从基数排序和二路归并排序中做选择，我选择了基数排序，并快速回忆了快速排序的例子，于是便很快的做出来了这道题。

插入排序

基本思想：

插入排序思想类似于扑克牌手牌整理
原数组为待起的未排序的手牌
起第一张牌不用整理，从起的第二张开始
和手牌里的牌进行比较，插入到手牌里

实现：

public static int[] insertSort(int[] sourceArray) {
    int s;
    int temp;
    for (int i = 1; i < sourceArray.length; i++) {
        temp = sourceArray[i];
        s = i;
        while (s > 0 && temp < sourceArray[s - 1]) {
            sourceArray[s] = sourceArray[s - 1];
            s = s - 1;
        }
        sourceArray[s] = temp;
    }
    return sourceArray;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

交换排序

冒泡排序

基本思想：

从左到右执行n次：比较相邻元素大小，谁大把谁放在右边

实现：

private static int[] bubbleSort(int[] sourceArray) {
    for (int i = 0; i < sourceArray.length; i++) {
        for (int j = 0; j < sourceArray.length - 1; j++) {
            sortMaxAndPutItRight(sourceArray, j, j+1);
        }
    }
    return sourceArray;
}

private static void sortMaxAndPutItRight(int[] sourceArray, int left, int right) {
    if (sourceArray[left] > sourceArray[right]) {
        int temp = sourceArray[right];
        sourceArray[right] = sourceArray[left];
        sourceArray[left] = temp;
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

快速排序

基本思想：

从左到右执行n次：
选基准元素（例如第一个元素），
左右两边往中间走，左边走的找到比他大的，右边走的找到比他小的
每次找到交换他们的顺序，直到左右走到一起
走到一起之后，选个元素和基准元素交换
——
然后在这个位置左边重复上述过程，右边也是

实现：

public static int[] quickSort(int[] sourceArray, int start, int end) {
    if (start < end) {
        int index = sortAndFindIndex(sourceArray, start, end);
        quickSort(sourceArray, start, index - 1);
        quickSort(sourceArray, index + 1, end);
    }
    return sourceArray;
}
private static int sortAndFindIndex(int[] sourceArray, int start, int end) {
    int temp = sourceArray[start];
    while (start < end) {
        while ((sourceArray[end] >= temp) && (start < end)) {
            end --;
        }
        sourceArray[start] = sourceArray[end];
        while ((sourceArray[start] <= temp) && (start < end)) {
            start ++;
        }
        sourceArray[end] = sourceArray[start];
    }
    sourceArray[start] = temp;
    return start;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

选择排序

简单选择排序

基本思想：

选择排序类似于扑克牌手牌里的出牌阶段

请到「今天看啥」查看全文