中级JAVA程序员应该掌握的数据结构知识

快乐斑马32

学习数据结构的重要性

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

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

                               
登录/注册后可看大图

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

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

                               
登录/注册后可看大图

为什么要综合比较

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

                               
登录/注册后可看大图

插入排序

基本思想：
插入排序思想类似于扑克牌手牌整理
原数组为待起的未排序的手牌
起第一张牌不用整理，从起的第二张开始
和手牌里的牌进行比较，插入到手牌里
实现：
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; }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[/list,交换排序

冒泡排序

基本思想：
从左到右执行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; } }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[*,15
[*,16
[/list,快速排序

基本思想：
从左到右执行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; }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[*,15
[*,16
[*,17
[*,18
[*,19
[*,20
[*,21
[*,22
[*,23
[/list,选择排序

简单选择排序

基本思想：
选择排序类似于扑克牌手牌里的出牌阶段
选择手牌里最小的牌打出去
打完之后，发现出的牌是有顺序的
实现：
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; }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[*,15
[*,16
[/list,堆排序

基本思想：待写
实现：待写
基数排序

基本思想
设最后一位设第一位（例如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; } } }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[*,15
[*,16
[*,17
[*,18
[*,19
[*,20
[*,21
[*,22
[*,23
[*,24
[*,25
[*,26
[*,27
[*,28
[*,29
[*,30
[*,31
[*,32
[*,33
[*,34
[*,35
[*,36
[*,37
[*,38
[*,39
[*,40
[*,41
[*,42
[*,43
[*,44
[*,45
[*,46
[/list,计数排序

基本思想
找到数组最大值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; }
[list,
[*,1
[*,2
[*,3
[*,4
[*,5
[*,6
[*,7
[*,8
[*,9
[*,10
[*,11
[*,12
[*,13
[*,14
[*,15
[/list,归并排序

二路归并排序

基本思想：待写
实现：待写