本文内容来自网络资源整理,若有错误,敬请指正。

java中的常用排序方法

java中常用的几种排序方法:选择排序、插入排序、快速排序、冒泡排序、归并排序、shell排序。
java 中的查找方法有:顺序查找法、二分查找法

选择排序

思路:在乱序数组中,假设第一位数最小,依次让后面的数与之比较,若遇到比它小的数就交换位置,一趟下来第一个数就是序列中最小的数,然后从第二个数开始重复操作。
public static void selectSort(int[] array) { int position = 0; for (int i = 0;
i <array.length; i++) { int j = i + 1; position = i; int temp = array[i]; for
(; j <array.length; j++) { if (array[j] < temp) { temp = array[j]; position =
j; } }array[position] = array[i]; array[i] = temp; }
System.out.println(Arrays.toString(array) + " selectSort"); }
插入排序

思路:如同玩扑克牌一样,每次摸牌都将它与手中的牌比较,始终将牌放在比它大的牌前面,比它小的牌后面。这样当牌全部摸到手上后,就是一个有序的序列。
public static void insertSort(int[] array) { for (int i = 1; i < array.length;
i++) {int temp = array[i]; int j = i - 1; for (; j >= 0 && array[j] > temp;
j--) {//将大于temp的值整体后移一个单位 array[j + 1] = array[j]; } array[j + 1] = temp; }
System.out.println(Arrays.toString(array) + " insertSort"); }
shell排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
先取一个正整数d1 < n, 把所有相隔d1的记录放一组,每个组内进行直接插入排序;然后d2 < d1,重复上述分组和排序操作;直至di =
1,即所有记录放进一个组中排序为止。

public static void shellSort(int[] array) { int i; int j; int temp; int gap = 1
;int len = array.length; while (gap < len / 3) { gap = gap * 3 + 1; } for (;
gap >0; gap /= 3) { for (i = gap; i < len; i++) { temp = array[i]; for (j = i -
gap; j >=0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j
+ gap] = temp; } } System.out.println(Arrays.toString(array) + " shellSort"); }
冒泡排序

思路:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
代码:
public static void bubbleSort(int[] array) { int temp = 0; for (int i = 0; i <
array.length - 1; i++) { for (int j = 0; j < array.length - 1 - i; j++) { if (
array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1
] = temp; } } } System.out.println(Arrays.toString(array) + " bubbleSort"); }
快速排序

快速排序是排序方法里面速率最快的一种方法,是对冒泡排序的一种改进, 属于不稳地排序。

public static void quickSort(int[] array) { _quickSort(array, 0, array.length -
1); System.out.println(Arrays.toString(array) + " quickSort"); } private static
int getMiddle(int[] list, int low, int high) { int tmp = list[low]; //数组的第一个作为中轴
while (low < high) { while (low < high && list[high] >= tmp) { high--; } list
[low] =list[high]; //比中轴小的记录移到低端 while (low < high && list[low] <= tmp) {
low++; }list[high] = list[low]; //比中轴大的记录移到高端 } list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置 } private static void _quickSort(int[] list, int low, int
high) {if (low < high) { int middle = getMiddle(list, low, high);
//将list数组进行一分为二 _quickSort(list, low, middle - 1); //对低字表进行递归排序 _quickSort(list
, middle +1, high); //对高字表进行递归排序 } }
归并排序

思路:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

代码:
public static void mergingSort(int[] array) { sort(array, 0, array.length - 1
); System.out.println(Arrays.toString(array) + " mergingSort"); } private static
void sort(int[] data, int left, int right) { if (left < right) { //找出中间索引 int
center = (left + right) /2; //对左边数组进行递归 sort(data, left, center); //对右边数组进行递归
sort(data, center +1, right); //合并 merge(data, left, center, right); } }
private static void merge(int[] data, int left, int center, int right) { int[]
tmpArr =new int[data.length]; int mid = center + 1; //third记录中间数组的索引 int third
= left;int tmp = left; while (left <= center && mid <= right) {
//从两个数组中取出最小的放入中间数组 if (data[left] <= data[mid]) { tmpArr[third++] =
data[left++]; }else { tmpArr[third++] = data[mid++]; } } //剩余部分依次放入中间数组 while
(mid <= right) { tmpArr[third++] = data[mid++]; }while (left <= center) {
tmpArr[third++] = data[left++]; }//将中间数组中的内容复制回原数组 while (tmp <= right) {
data[tmp] = tmpArr[tmp++]; } }
shell排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
先取一个正整数d1 < n, 把所有相隔d1的记录放一组,每个组内进行直接插入排序;然后d2 < d1,重复上述分组和排序操作;直至di =
1,即所有记录放进一个组中排序为止。

代码:
public static void shellSort(int[] array) { int i; int j; int temp; int gap = 1
;int len = array.length; while (gap < len / 3) { gap = gap * 3 + 1; } for (;
gap >0; gap /= 3) { for (i = gap; i < len; i++) { temp = array[i]; for (j = i -
gap; j >=0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j
+ gap] = temp; } } System.out.println(Arrays.toString(array) + " shellSort"); }
查找算法

java中常用的查找算法有顺序查找和二分查找。顺序查找也许效率较低,二分查找效率高,但是要在序列是在有序的情况下。顺序查找这里不在赘述。

二分查找

前提条件:已排序的数组中查找

二分查找的基本思路是:首先确定该查找区间的中间点位置: int mid = (low+upper) /
2;然后将待查找的值与中间点位置的值比较:若相等,则查找成功并返回此位置。若中间点位置值大于待查值,则新的查找区间是中间点位置的左边区域。若中间点位置值小于待查值,则新的查找区间是中间点位置的右边区域。下一次查找是针对新的查找区间进行的。

图例说明:

原始数据: int[] a={5,3,6,1,9,8,2,4,7}; 查找是否存在数字8;

第一步,先用之前学过的排序方法将数组按升序排序:int[] a={1,2,3,4,5,6,7,8,9};

第二步,取中间数:5跟8比较,8大于5 ,取中间数右侧的数组进行比较,即{6,7,8,9}

第三步:重复第一步和第二步,直到找到数据或者比较完所有数据。

代码:
import java.util.Scanner; /* * 二分查找 */ public class BinarySearch { public
static void main(String[] args) { int[] arr={5,3,6,1,9,8,2,4,7}; //先打印输出原始数组数据
System.out.println("原始数组数据如下:"); for (int n : arr) { System.out.print(n+" "); }
System.out.println(); //首先对数组进行排序,这里用冒泡排序 for(int i=0;i<arr.length-1;i++){ for(
int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ int temp=arr[j];
arr[j]=arr[j+1]; arr[j+1]=temp; } } } //遍历输出排序好的数组 System.out.println(
"经过冒泡排序后的数组:"); for(int n:arr){ System.out.print(n+" "); } System.out.println();
//换行 Scanner input=new Scanner(System.in); System.out.println("请输入你要查找的数:"); int
num=input.nextInt();int result=binarySearch(arr, num); if(result==-1){ System.
out.println("你要查找的数不存在……"); } else{ System.out.println("你要查找的数存在,在数组中的位置是:"
+result); } }//二分查找算法 public static int binarySearch(int[] arr,int num){ int
low=0; int upper=arr.length-1; while(low<=upper){ int mid=(upper+low)/2; if
(arr[mid]<num){ low=mid+1; } else if(arr[mid]>num){ upper=mid-1; } else return
mid; }return -1; } }

技术
©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语言(猜数字小游戏)