<>学习数据结构的重要性

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

<>算法复杂度比较

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

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

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

<>为什么要综合比较

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

<>插入排序

基本思想:

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

实现:
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; }
<>归并排序
<>二路归并排序
基本思想:待写
实现:待写

<>推荐书籍

《数据结构教程(第三版)》

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信