王道考研系列–数据规划温故而知新,打好基础才干走得更远。
一、根柢概念
1、数据规划的根柢概念
数据:是信息的载体,是描绘客观事物特征的数、字符以及一切能输入到核算机中并被核算机程序辨认和处置的符号的集结。
规划:数据元素彼此之间的联络叫做“规划”
数据规划:彼此之间存在一种或多种特定联络的数据元素的集结。
数据规划包括三方面内容:逻辑规划、存储规划、数据的运算。
2、算法的根柢概念
算法:特定疑问求解进程的一种描绘
特性:有穷性、断定性、可行性、输入、输出
算法功率的衡量:
1、时刻凌乱度:最深层循环内的语句的频率。
常见的时刻凌乱度:
o(1)<o(log2n)<o(n)<o(nlog2n)<o(n^2)<o(n^3)<o(2^n)<o(n!)<o(n^n)
2、空间凌乱度:s(n),算法所耗费的存储空间
二、线性表
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。
次序表由数组下标、数据元素构成。
次序表不必定是数据依照巨细排序的线性表。
线性表的链式标明
1、单链表 单链表的查找、刺进、删去操作
2、双链表 双链表的刺进、删去操作
3、循环链表
三、栈和行列
栈的界说:只答应在一端进行刺进、删去操作的线性表
特征: 后出
行列的界说:只答应在表的一端进行刺进,在表的另一端进行删去。
特征: 先出
四、树、二叉树
1、二叉树的遍历
前序遍历、中序遍历、后序遍历
五、图
往常工刁难图的使用不是许多,是我平常触摸的景象太low了吗?
六、查找
1、次序查找:从线性表的一端初步,逐个查看要害词是不是满足条件。找到则回来成功,没找到,则回来失利。
int ordersearch(int searchkey, int[] array) {
if (array == null || array.length < 1) {
return -1;
}
for (int i = 0; i < array.length; i++) {
if (searchkey == array[i]) {
return array[i];
}
}
return -1;
}
2、二分查找
int binarysearch(int searchkey, int[] array) {
int low = 0;
int high = array.length -1;
while(low <= high) {
int middle = (low + high) / 2;
if (searchkey > array[middle]) {
low = middle + 1;
} else if (searchkey < array[middle]) {
high = middle - 1;
} else {
return middle;
}
}
return -1;
}
3、分块查找
/**
* 分块查找
*
* @param index 索引表,存放各块的最大值
* @param st 次序表
* @param key 查找要害词
* @param m 次序表中各块长度相等
* @return
*/
int blocksearch(int[] index, int[] st, int key, int m) {
int i = binarysearch(key, index);
if (i >= 0) {
int j = i > 0 ? i * m : i;
int len = (i + 1) * m;
// 在断定的块顶用次序查找办法查找key
for (int k = j; k < len; k++) {
if (key == st[k]) {
return k;
}
}
}
return -1;
}
4、散列表
之前的查找都是根据比照进行查找,hash表是经过哈希函数直接求出结点的地址,是要害词到地址的直接变换办法。
(1)哈希函数:一个把查找表中的要害词映射为该要害词对应的地址的函数。
(2)散列表:根据要害词而直接进行造访的数据规划。
处置冲突的办法:
(1)翻开定址法:假定两个数据元素的哈希值相同,则在哈希表中为后刺进的数据元素另外选择一个表项。当程序查找哈希表时,假定没有在第一个对应的哈希表项中找到契合查找需求的数据元素,程序就会持续往后查找,直到找到一个契合查找需求的数据元素,或许遇到一个空的表项。
(2)拉链法:将哈希值相同的数据元素存放在一个链表中,在查找哈希表的进程中,当查找到这个链表时,有必要选用线性查找办法。
/**
* hash查找
*
* @param hash
* @param hashlength
* @param key
* @return
*/
int searchhash(int[] hash, int hashlength, int key){
int hashaddress = key % hashlength; // 除留余数法
// 指定的hashaddress对应值存在但不是要害值,则用翻开寻址法持续定位
while (hash[hashaddress] != 0 && hash[hashaddress] != key) {
hashaddress = (++hashaddress) % hashlengt
h;
}
// 查找到了翻开单元,标明查找失利
if (hash[hashaddress] == 0) {
return -1;
}
return hashaddress;
}
七、排序
1、排序的概念:从头摆放表中的元素,使表中的元素满足依照要害词递加或递减的进程。
2、刺进排序:直接刺进排序、减半刺进排序、希尔排序
直接刺进排序:将元素从无序子序列取出,刺进有序序列子序列中。
private static void insertsort(int[] array) {
int n = array.length;
int i,j;
for (i = 1; i < n; i++) { // 无序列表的第一位比照数据就是index = 1的数据
int temp = array[i]; // 本次循环,待刺进有序列表的数
// 以下遍历有序表,从后往前查找待刺进方位
// 无序列表取出的temp小于前驱,则无序列表一切元素向后移一位
for (j = i- 1; j >= 0 && temp < array[j]; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp; // 刺进元素
}
// 打印成果
system.out.print("排序成果:");
for (int k = 0; k < array.length; k++) {
system.out.print(" " + array[k]);
}
}
减半刺进法:在遍历有序表查找待刺进元素方位时运用二分查找法进行刺进方位的断定,其他思路和直接刺进法坚持共同。
private static void midinsertsort(int[] array) {
int n = array.length;
int i, j, low, high, mid;
for (i = 1; i < n; i++) {
int temp = array[i];
// 以下为二分法在有序表中查找刺进方位
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp > array[mid]) { // 阐明temp的方位在左半有些
low = mid + 1;
} else { // 阐明temp的方位在有半有些
high = mid - 1;
}
}
// 有序表的元素向后移一位
for (j = i - 1; j >= 0 && temp < array[j]; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp; // 刺进元素
}
// 打印成果
system.out.print("排序成果:");
for (int k = 0; k < array.length; k++) {
system.out.print(" " + array[k]);
}
}
希尔排序:将整个无序序列切割成若干个子序列(由相隔某个“增量”的元素构成的)别离进行直接刺进排序,然后顺次减缩增量再进行排序,待整个序列中的元素根柢有序时,再对全体元素进行一次直接刺进排序。
https://www.cnblogs.com/snowcan/p/6244391.html
2、交流排序:冒泡排序、快速排序
冒泡排序:对未排序规模内的相邻两个数进行比照,若后者比前者小,则交换方位,否则进入下一位持续比照(默许依照升序摆放)
private static void bubblesort(int[] array) {
int n = array.length;
boolean exchange;
for (int i = 0; i < n; i++) {
exchange = false;
for (int j = 0; j < n - (i + 1); j++) { // 这儿只对未排序有些进行遍历比照
if (array[j] > array[j + 1]) {
exchange = true;
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
if(!exchange) // 无序交换,跳出循环,进行下一次比照
break;
}
// 打印成果
system.out.print("排序成果:");
for (int k = 0; k < array.length; k++) {
system.out.print(" " + array[k]);
}
}
快速排序:经过一趟排序即将排序的数据切割成独立的两有些,使其间一有些比另一有些一切数据都要小,然后再按此办法对这两有些数据别离进行快速排序,整个排序进程可以递归进行,以此抵达整个数据变成有序序列。
算法进程:
1.设置 low=0, high=n-1。
2.选择一个基准元素赋值给temp,即temp=a[low]。
3.从high初步向前查找,即由后初步向前查找(high–),找到第一个小于temp的值,将a[high]和a[low]交流。
4.从low初步向前后查找,即由前初步向后查找(low++),找到第一个大于temp的值,将a[high]和a[low]交流。
5.重复第3步和第4步,直到 low==high ,3,4步中,若没找到契合条件的值,实施 high– 或 low++ ,直到找到中止。进行交流时 low和high的方位不变。当low==high时循环结束。
private static void quicksort(int[] array, int low, int high) {
if (low < high) {
/**
* 将数组一分为二
*/
int middle = getmiddle(array, low, high);
/**
* 将小于基准元素的数据进行递归排序
*/
quicksort(array, low, middle - 1);
/**
* 将大于基准元素的数据进行递归排序
*/
quicksort(array, middle + 1, high);
}
}
private static int getmiddle(int[] array, int low, int high) {
int temp = array[low]; // 数组第一个元素为基准元素
while (low < high) {
while (low < high && array[high] > temp) {
high--;
}
/**
* 比基准小的数据移到低端
*/
array[low] = array[high];
while (low < high && array[low] < temp) {
low++;
}
/**
* 比基准大的记载移到高端
*/
array[high] = array[low];
}
/**
* 此时 low == high
*/
array[low] = temp;
return low;
}
3、选择排序:简略选择排序、堆排序
简略选择排序:在待排序数据中,选出最小的一个数与第一个方位的数交流;然后在剩下的数中选出最小的数与第二个数交流;顺次类推,直至循环到只剩下两个数进行比照中止。
0.初始状况 3,1,5,7,2,4,9,6(共8个数)
1.n=8 个数中,最小数值为1,与第一个数交流:1,3,5,7,2,4,9,6
2.剩下 n-1=7 个数中,最小数值为2,与第二个数交流:1,2,5,7,3,4,9,6
3.剩下 n-2=6 个数中,最小数值为3,与第三个数交流:1,2,3,7,5,4,9,6
4.剩下 n-3=5 个数中,最小数值为4,与第四个数交流:1,2,3,4,5,7,9,6
5.剩下 n-4=4 个数中,最小数值为5,与第五个数交流:1,2,3,4,5,7,9,6
6.剩下 n-5=3 个数中,最小数值为6,与第五个数交流:1,2,3,4,5,6,9,7
7.剩下 n-6=2 个数中,最小数值为7,与第五个数交流:1,2,3,4,5,6,7,9
private static void selectsort(int[] array) {
int n = array.length;
for (int i = 0; i < n; i++) {
int k = i;
for (int j = i + 1; j < n; j++) {
if (array[j] < array[i]) {
k = j;
}
}
if (k != i) { // 阐明需要换位了,后一位比前一位小
int temp = array[i];
array[i] = array[k];
array[k] = temp;
}
print(array, n, i);
}
printresult(array, n);
}
private static void print(int[] a, int n, int i) {
// todo auto-generated method stub
system.out.print("第" + i + "次:");
for (int j = 0; j < n; j++) {
system.out.print(" " + a[j]);
}
system.out.println();
}
private static void printresult(int[] a, int n) {
system.out.print("究竟排序成果:");
for (int j = 0; j < n; j++) {
system.out.print(" " + a[j]);
}
}
堆排序:概况看外部联接
https://www.cnblogs.com/snowcan/p/6595813.html
另外还有归并排序、基数排序、外部排序,概况请查看其他材料。
end…