数据结构和算法

一。为什么要学习数据结构？
数据结构是编程的基础。
编程水平 = 数据结构基础 + 算法 + 设计模式

1.什么是数据结构？
数据结构是研究非数值计算的程序中的操作对象，以及这些操作对象之间的关系与操作。

2. 时间复杂度大小比较：
O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方）< O(n的立方) < O(2的n次方) < O(n!) < O(n的n次方)

O(log(n)) 的时间复杂度：如对二叉树的查找，每次可排除一半。
int count = 1;
while (count < n) {
count = count * 2;
}


3. 算法的五个特性：
1）输入
2）输出
3）有穷性
4）确定性
5）可行性

4. 算法设计追求的目标：（写程序时要从这4点考虑）
1）正确性 ： 把各种可能考虑到
2）可读性 ： 加注释
3）健壮性 ： 无论何种情况，不能让程序挂掉，对Exception要做处理
4）时间和空间复杂度 ： 算法优劣的关键

二.栈、队列、链表、二叉树的底层实现

线性存储可分为：数组 和 链表

数组和链表都可实现：
栈和队列

1. 栈：底层实现是数组 --> 先进后出
成员变量：
private long[] arr;
private int top; //用于标记栈顶的元素，以方便出栈。（所谓栈顶元素，就是数组的最后一个元素）

2. 队列：底层实现是数组 --> 先进先出
成员变量：
private long[] arr;
private int size; //有效元素个数
private int front; //队头
private int end; //队尾

3. 链表：相对于数组（连续的存储空间），链表是不连续的存储空间
成员变量：
private long data; //数据域
private Node next; //指针域

4. 二叉树
成员变量：
private long data;
private BTree left;//左子树
private BTree right;//右子树

三. 数据结构中经典算法：
1. 二分法查找
前提：数据必须有序
要求：查找指定的值在有序的数组中，返回对应数组元素下标。
算法：用当前元素与中间大小元素比较，若小于，则取左边子数组的中间元素做比较。
    public static int binarySearch(int[] arr, int key) {
        int start = 0;
        int end = arr.length - 1;
        if (key < arr[0] || key > arr[end]) {
return -1;
}
        while (start <= end) {
            int middle = (start + end) / 2;
            if (key < arr[middle]) {
                end = middle - 1;
            } else if (key > arr[middle]) {
                start = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

2. 八种排序算法：
分类：
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（基数排序）

所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序，堆排序。


（1）插入排序
1）直接插入排序
算法思想：在需要排序的一组数中，假设前面n-1(其中n>=2)个数已经是排好序的，现在要把第n个数插入到前面的有序数组中。如此往复循环，直至所有数都排好序。



public static void insertSort(int[] arr) {
        int tmp;
        int j = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                tmp = arr[i];
                // 从“比tmp大的数”到a[j], 数据向右移动一位
                for (j = i - 1; j >= 0 && tmp < arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = tmp; //把tmp移动到原来a[j]即a[i - 1]的地方，因为左右执行了j--, 所以arr[j + 1] = tmp;
            }
            System.out.print("第" + (i + 1) + "次：");
            for (int t : arr) {
                System.out.print(t + " ");
            }
            System.out.println();
        }
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

2) 希尔排序（shell排序）
算法思想：将要排序的数组按某个增量d(d=n/2; n是要排序数组的元素个数）分成若干组，每组记录的下标相差d, 然后对每组中的元素进行直接插入排序，然后再用一个较小的增量(d/2) 对它进行分组，再对每组中的元素进行直接插入排序。当增量减到1时，执行直接插入排序后，排序完成。



（2）交换排序
1） 冒泡排序
基本思想：对于要排序的数组，对未排序的范围内的元素，自左到右对相邻两个数做比较，数大的向右移动，数小的向左移动。即：当发现左边比右边的数大时，交互他俩的位置。



public static void bubbleSourt(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 每次把最大的数放到最右边
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

2）快速排序
基本思想：选择一个基准元素（通常选择第一个元素或者最后一个元素），然后将需要排序的数组分成两部分，一部分比基准元素小，一部分比基准元素大或等于。此时，基准元素就在整个数组的正确位置。然后再用同样的方法递归地排序划分的两部分。

快速排序在元素少时效率不好，这时可以用插入排序。



public class QuickSort {

public static int getBase(int[] arr, int low, int high) {
int base = arr[low];
while (low < high) {
while (low < high && base <= arr[high]) {
high--;
}
arr[low] = arr[high];

while (low < high && arr[low] <= base) {
low++;
}
arr[high] = arr[low];
}

arr[low] = base;
return low;
}

public static void sort(int[] arr, int low, int high) {
if (low < high) {
int base = getBase(arr, low, high);
sort(arr, low, base);
sort(arr, base + 1, high);
}
}

public static void main(String[] args) {
int arr[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25,
53, 51 };
sort(arr, 0, arr.length - 1);
for (int e : arr) {
System.out.print(e + " ");
}
}

}

(3) 选择排序
1）简单选择排序
基本思想：在要排序的数组中，选出最小的数与第一个数交换位置；然后再剩下的数当中找出最小的数与第二个数交换位置，如此循环，知道倒数第二个数与最后一个数交换位置。



2）堆排序
基本思想：堆排序是树形选择排序，是对简单选择排序的改进。
堆：完全二叉树，且堆顶元素大于（或小于）其左右节点



(4) 归并排序（Merge排序）
基本思想：将两个（或两个以上）的有序表合并成一个新的有序表，即把待排序的数组分为若干个子数组，每个子数组都是有序的，然后再把有序的子数组合并成一个整体有序的数组。



(5) 基数排序
基本思想：将所有待排序的数值（正整数）统一为统一的数位长度，将数位较短的数前面补零。然后，从最低位开始，一次进行一次排序。这样，从最低位排序一直到最高位排序完成以后，数列就变成了一个有序的序列。



3. 排序算法的时间空间复杂度：



Java常用排序算法原文地址：http://www.importnew.com/16266.html