黑马程序员技术交流社区
标题: 【成都校区】Java 常用排序算法 [打印本页]
作者: 小刀葛小伦 时间: 2019-11-1 13:39
标题: 【成都校区】Java 常用排序算法
面试中经常会被问到或现场写：冒泡、快速
（1）冒泡排序 Bubble Sort
[Java] 纯文本查看 复制代码
/**
- 冒泡排序
- @param arr 需要排序的数组
*/
public void bubbleSort(int[] arr){
for(int i= 0;i<arr.length;i++){
for(int j = 0;j<arr.length-i-1;j++){
if(arr[j] > arr[j+1]){
int temp;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.print(arr + ",");
}
}
（2）插入排序 Insert Sort
[Java] 纯文本查看 复制代码
/**
- 插入排序
- @param arr 需要排序的数组
*/
public static void insertSort(int[] arr){
int length=arr.length; //数组长度
int j; //当前值的位置
int i; //指向j前的位置
int key; //当前要进行插入排序的值
//61,19,56,37,20 ,66,50,34,37,3
// 19 37 56 61
/*
key = 20
j =4;
i = j-1 = 3
a[4] = a[3]
19 37 56 61 61
i = 2 56 > 20
a[3]=a[2]
19 37 56 56 61
i = 1 37 > 20
a[2] = a[1]
19 37 37 56 61
i =0 19 > 20 false
a[1] = key =20
*/
//从数组的第二个位置开始遍历值
for(j=1;j<length;j++){
key=arr[j];
i=j-1;
//a比当前值大时，a后移一位,空出i的位置，好让下一次循环的值后移
while(i>=0 && arr>key){
arr[i+1]=arr; //将a值后移
i--; //i前移
}//跳出循环(找到要插入的中间位置或已遍历到0下标)
arr[i+1]=key; //将当前值插入
}
}
（3）选择排序 Select Sort
[Java] 纯文本查看 复制代码
/**
- 选择排序
- @param arr 需要排序的数组
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i; / 将当前下标定义为最小值下标
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) { /* 如果有小于当前最小值的关键字 */
min = j; /* 将此关键字的下标赋值给min */
}
}
if (i != min) {/* 若min不等于i，说明找到最小值，交换 */
int tmp = arr[min];
arr[min] = arr;
arr = tmp;
}
}
}
（4）归并排序 Merge Sort
[Java] 纯文本查看 复制代码
/**
- 归并排序
- @param a 需要排序的数组
- @param s 第一个有序表的起始下标
- @param m 第二个有序表的起始下标
- @param t 第二个有序表的结束下标
- */
public static void merge(int[] arr, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (arr <= arr[j]) {
tmp[k] = arr;
k++;
i++;
} else {
tmp[k] = arr[j];
// sum += (j - i) - (j - m);
j++;
k++;
}
}
while (i < m) {
tmp[k] = arr;
i++;
k++;
}
while (j <= t) {
tmp[k] = arr[j];
j++;
k++;
}
System.arraycopy(tmp, 0, arr, s, tmp.length);
}
（5）快速排序 Quick Sort
[Java] 纯文本查看 复制代码
/**
* 获得基础的下标
* @param arr 需要排序的数组
* @param low 数组待排序的最小的下标
* @param high 数组待排序的最大的下标
* @return 返回中轴值（该值大于左边值，小于右边值）
*/
public static int getMiddle(int[] arr,int low,int high){
int temp = arr[low];// temp = 12 = arr[0]
while(low <high){// 0<1
while(low <high && arr[high] > temp){//0<1 && 14>12
high--;//h = 0
}
arr[low] = arr[high]; // a[0] = a[0];
while(low <high && arr[low] <=temp){//
low++;
}
arr[high] = arr[low];//a[0] = a[0]
}
arr[low] = temp;//a[0] = 12
return low;//0
}
public static void quickSort(int[] arr,int low, int high){
if(low <high){//0,1
//将数组一份为二
int middle = getMiddle(arr, low, high);// arr 0,9 m = 4
System.out.println("middle = " + middle);//m =4
//左边进行递归 快速排序
quickSort(arr,low,middle -1); // arr 0,3
//右边进行递归 快速排序
quickSort(arr,middle + 1,high);// arr 5,9
}
}
//再次封装，对外调用 12，14
public static void quick(int[] arr){
if(arr.length >=2)
quickSort(arr, 0, arr.length -1);// 0,9
}
int[] a ={}
int[] a ={65}
int[] a ={65,76}
//再次封装，对外调用 12，14
public static void quick(int[] arr){
if(arr.length >=2)
quickSort(arr, 0, arr.length -1);// 0,9
}
int[] a ={}
int[] a ={65}
int[] a ={65,76}
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |