H5W3
当前位置:H5W3 > java > 正文

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

学习数据结构的重要性

https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3486437067…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
https://xueqiu.com/3554997958…
程序=数据结构 + 算法,算法很重要,数据结构也很重要,只有掌握了这两者,我们才等于掌握了写程序的本领,才是合格的程序员哦。

算法复杂度比较

在网上看到的一篇总结,这个要背的。
【Java】中级JAVA程序员应该掌握的数据结构知识

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

这是我学数据结构的时候做的一个总结:
【Java】中级JAVA程序员应该掌握的数据结构知识

为什么要综合比较

见下图,这是一道排序算法的面试题(要求:稳定,快速),我在做这道题的时候,根据我总结的内容,很快便锁定了算法,首先,算法要求一个稳定,快速的算法,我们便可以确定要从基数排序和二路归并排序中做选择,我选择了基数排序,并快速回忆了快速排序的例子,于是便很快的做出来了这道题。
【Java】中级JAVA程序员应该掌握的数据结构知识

插入排序

基本思想:

实现:

`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

交换排序

冒泡排序

基本思想:

实现:

`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
快速排序

基本思想:

实现:

`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

选择排序

简单选择排序

基本思想:

实现:

`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;
}`
*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15
*   16
堆排序

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

基数排序

基本思想

实现

`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;
}
}
}`
*   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

计数排序

基本思想

实现

`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;
}`
*   1
*   2
*   3
*   4
*   5
*   6
*   7
*   8
*   9
*   10
*   11
*   12
*   13
*   14
*   15

归并排序

二路归并排序

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

本文地址:H5W3 » 【Java】中级JAVA程序员应该掌握的数据结构知识

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址