学习数据结构的重要性
程序＝数据结构 + 算法，算法很重要，数据结构也很重要，只有掌握了这两者，我们才等于掌握了写程序的本领，才是合格的程序员哦。
算法复杂度比较
在网上看到的一篇总结，这个要背的。
数据结构重点：排序算法比较
这是我学数据结构的时候做的一个总结：
为什么要综合比较
见下图，这是一道排序算法的面试题（要求：稳定，快速），我在做这道题的时候，根据我总结的内容，很快便锁定了算法，首先，算法要求一个稳定，快速的算法，我们便可以确定要从基数排序和二路归并排序中做选择，我选择了基数排序，并快速回忆了快速排序的例子，于是便很快的做出来了这道题。
插入排序
基本思想：
插入排序思想类似于扑克牌手牌整理
原数组为待起的未排序的手牌
起第一张牌不用整理，从起的第二张开始
和手牌里的牌进行比较，插入到手牌里
实现：
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;}
交换排序
冒泡排序
基本思想：
从左到右执行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;}}
快速排序
基本思想：
从左到右执行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;}
选择排序
简单选择排序
基本思想：
选择排序类似于扑克牌手牌里的出牌阶段
选择手牌里最小的牌打出去
打完之后，发现出的牌是有顺序的
实现：
public static int[] selectionSort(int[] sourceArray) {for (int i = 0; i < sourceArray.length - 1; i++) {int min = i;for (int j = i + 1; j < sourceArray.length; j++) {min = sourceArray[j] < sourceArray[min] ? j : min;}swap(sourceArray, i, min);}return sourceArray;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
堆排序
基本思想：待写
实现：待写
基数排序
基本思想
设最后一位设第一位（例如352的2），倒数第二位是第二位
将数字按照第一位进行排序
将数字按照第二位进行排序
数字相同的保持位置不变
实现
public static int getNumInPos(int num, int pos) {int tmp = 1;for (int i = 0; i < pos - 1; i++) {tmp *= 10;}return (num / tmp) % 10;}public static int getMaxDigit(int[] a) {int max = a[0];for (int i = 0; i < a.length; i++) {if (a[i] > max) {max = a[i];}}int tmp = 1, d = 1;while (true) {tmp *= 10;if (max / tmp != 0) {d++;} else {break;}}return d;}public static void radixSort(int[] a, int d) {int[][] array = new int[10][a.length + 1];for (int i = 0; i < 10; i++) {array[i][0] = 0;}for (int pos = 1; pos <= d; pos++) {for (int i = 0; i < a.length; i++) { int row = getNumInPos(a[i], pos);int col = ++array[row][0];array[row][col] = a[i];}for (int row = 0, i = 0; row < 10; row++) { for (int col = 1; col <= array[row][0]; col++) {a[i++] = array[row][col];}array[row][0] = 0; }}}
计数排序
基本思想
找到数组最大值l，创建一个长度为l的新数组
将原数组的值作为新数组的下标，有几个，下标对应的数就是几
将新数组从左到右遍历，赋值给原数组
实现
private static int[] countSort(int[] array) {int maxVal = Arrays.stream(array).max().getAsInt();int[] sortList = new int[maxVal + 1];for (int i : array) {sortList[i]++;}int sortedIndex = 0;for (int i = 0; i < (maxVal + 1); i++) {while (sortList[i] > 0) {array[sortedIndex++] = i;sortList[i]--;}}return array;}
归并排序
二路归并排序
基本思想：待写
实现：待写
推荐书籍
《数据结构教程(第三版)》
