一、介绍几种常见的排序算法:直接插入排序、简单选择排序、冒泡排序、快速排序。

1、直接插入排序

描述:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,
现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。
如此反复循环,直到全部排好顺序。 

算法:从第二个数(当前数)开始,拿它与前一个数(比较数)比较
--如果比较数大于当前数,则让比较数往后移动一位,再拿当前数与比较数的前一位对比,依次类推
--否则,在该位置插入当前数

代码实现:
public static void Zhijie(int[] array) { for (int i = 1; i < array.length;
i++) { int temp = array[i]; int j = i - 1; for (; j >= 0; j--) { if (array[j] >
temp) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = temp; } }
2、简单选择排序

描述:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

也就是说,先拿第一个跟第二个、第三个、第四个...比,比完之后第一个最小;然后拿第二个跟第三个、第四个、第五个...比,比完之后第二个最小;以此类推。

代码实现:
public static void Jiandan(int[] array) { for (int i = 0; i < array.length -
1; i++) { for (int j = i + 1; j < array.length; j++) { if (array[i] > array[j])
{ int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } }
3、冒泡排序

描述:比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码实现:
public static void Maopao(int[] array) { for (int i = array.length - 1; i > 0;
i--) { for (int j = 0; j < array.length - 1; j++) { if (array[j] > array[j +
1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }
4、快速排序

描述:把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比它小交换,比它大不做任何处理;交换了以后再和小的那端比,比它小不交换,比他大交换。这样循环往复,一趟排序完成,左边就是比中轴小的,右边就是比中轴大的,然后再用分治(递归)法,分别对这两个独立的数组进行排序。 

代码实现:
public static void Kuaisu(int[] array) { if (array.length > 0) { _quick(array,
0, array.length - 1); } } // 递归 private static void _quick(int[] array, int
low, int hight) { if (low < hight) { int mid = quick(array, low, hight);
_quick(array, 0, mid - 1); _quick(array, mid + 1, hight); } } // 找中轴 private
static int quick(int[] array, int low, int hight) { int temp = array[low];
while (low < hight) { while (low < hight && array[hight] > temp) { hight--; }
array[low] = array[hight]; while (low < hight && array[low] < temp) { low++; }
array[hight] = array[low]; } array[low] = temp; return low; }
二、介绍几种常见的查找算法:顺序查找、二分查找、分块查找、哈希查找。

直接上代码:
/** * 顺序查找平均时间复杂度 O(n) * * @param searchKey * 要查找的值 * @param array *
数组(从这个数组中查找) * @return 查找结果(数组的下标位置) */ public static int orderSearch(int
searchKey, int[] array) { if (array == null || array.length < 1) return -1; for
(int i = 0; i < array.length; i++) { // 遍历数组,直到找到为止 if (array[i] == searchKey)
{ return i; } } return -1; } /** * 二分查找又称折半查找,它是一种效率较高的查找方法。
【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。 * * @param array * 有序数组 * * @param
searchKey * 查找元素 * * @return searchKey的数组下标,没找到返回-1 */ public static int
binarySearch(int[] array, int searchKey) { // 二分查找之非递归 int low = 0; // 第一个索引
int high = array.length - 1; // 最后一个最高位索引 while (low <= high) { int middle =
(low + high) / 2; // 中间位置索引 if (searchKey == array[middle]) { //
如果等于中间值,找到了,直接返回 return middle; } else if (searchKey < array[middle]) { //
如果查找值小于中间值 high = middle - 1; // 在前面一块继续二分查找 } else { // 如果查找值大于中间值 low =
middle + 1; // 在后面一块继续二分查找 } } return -1; } public static int BinSearch(int
Array[], int low, int high, int key/* 要找的值 */) { // 二分查找之递归 if (low <= high) {
int mid = (low + high) / 2; if (key == Array[mid]) { return mid; } else if (key
< Array[mid]) { return BinSearch(Array, low, mid - 1, key); } else if (key >
Array[mid]) { return BinSearch(Array, mid + 1, high, key); } } else { return
-1; } return -1; } /** * 分块查找 *
1.首先将查找表分成若干块,在每一块中数据元素的存放是任意的,但块与块之间必须是有序的(假设这种排序是按关键字值递增的,也就是说在第一块中任意一个 *
数据元素的关键字都小于第二块中所有数据元素的关键字,第二块中任意一个数据元素的关键字都小于第三块中所有数据元素的关键字,依次类推); *
2.建立一个索引表,把每块中最大的关键字值按块的顺序存放在一个辅助数组中,这个索引表也按升序排列; *
3.查找时先用给定的关键字值在索引表中查找,确定满足条件的数据元素存放在哪个块中,查找方法既可以是折半方法,也可以是顺序查找。 *
4.再到相应的块中顺序查找,便可以得到查找的结果。 * * @param index * 索引表,其中放的是各块的最大值 * @param st * 顺序表,
* @param key * 要查找的值 * @param m * 顺序表中各块的长度相等,为m * @return */ public static int
blockSearch(int[] index, int[] st, int key, int m) { //
在序列st数组中,用分块查找方法查找关键字为key的记录 // 1.在index[ ] 中折半查找,确定要查找的key属于哪个块中 int i =
binarySearch(index, key); 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]) { System.out.println("查询成功"); return k; } } }
System.out.println("查找失败"); return -1; } /** *
哈希表查找是通过对记录的关键字值进行运算,直接求出结点的地址,是关键字到地址的直接转换方法,不用反复比较。假设f包含n个结点,Ri为其中某个结点(1≤i≤n),keyi是其关键字值,在keyi与Ri的地址之间建立某种函数关系,可以通过这个函数把关键字值转换成相应结点的地址,有:addr(Ri)=H(keyi),addr(Ri)为哈希函数。
* 解决冲突的方法有以下两种: (1)开放地址法 *
如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。
* (2)链地址法 将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。 Hash查找 * *
@param hash * @param hashLength * @param key * @return */ public static int
searchHash(int[] hash, int hashLength, int key) { // 哈希函数 int hashAddress = key
% hashLength; // 指定hashAdrress对应值存在但不是关键值,则用开放寻址法解决 while (hash[hashAddress] !=
0 && hash[hashAddress] != key) { hashAddress = (++hashAddress) % hashLength; }
// 查找到了开放单元,表示查找失败 if (hash[hashAddress] == 0) return -1; return hashAddress; }
/** * 数据插入Hash表 * * @param hash * 哈希表 * @param hashLength * @param data */
public static void insertHash(int[] hash, int hashLength, int data) { // 哈希函数
int hashAddress = data % hashLength; // 如果key存在,则说明已经被别人占用,此时必须解决冲突 while
(hash[hashAddress] != 0) { // 用开放寻址法找到 hashAddress = (++hashAddress) %
hashLength; } // 将data存入字典中 hash[hashAddress] = data; }
 

技术
©2019-2020 Toolsou All rights reserved,
python中delete怎么用_python中如何使用np.delete()方法?大厂Java岗春招必看:论一个面渣逆袭之路上必学得那些知识点3 4j不是合法的python表达式_3+4j不是合法的Python表达式。SQL综合题 员工单位综合题pyqt按钮调用python程序_PyQt:链接按钮到程序中的函数找出游戏的获胜者(java)看完这个去面试,稳过~~将硬盘转换成GPT分区格式python常用内置函数C语言(猜数字小游戏)