Java教程
排序算法
本文主要是介绍排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
内部排序算法
分类
- 插入排序
- 直接插入排序
- 折半插入排序
- 希尔排序
- 交换排序
- 冒泡排序
- 快速排序
- 选择排序
- 简单选择排序
- 堆排序
- 归并排序
- 基数排序
直接插入排序
-
算法思想
对于一组数据，只有一个数时，一定有序。因此只需要从第二个数开始确定它在有序序列中的位置，然后将其移到该位置
-
算法实现步骤
/** * 直接插入排序（从小到大） * 从第二位开始，依次向前比较，如果遇到比它大的移动位置 */ public static void insertDirectly(int[] A) { int[] array = A; System.out.println("初始："); inputArray(array); int len = array.length; for (int i = 1; i < len; i++) { // 0 到 i - 1 这个序列一定是有序的，若 array[i] > array[i - 1] 此时的元素已经在它应在的位置上 // 所以只需要考虑当前元素在有序序列中的位置 for (int j = i; j > 0 && array[j] < array[j - 1]; j--) { array[j] = array[j] ^ array[j - 1]; array[j - 1] = array[j] ^ array[j - 1]; array[j] = array[j] ^ array[j - 1]; } } System.out.println("直接插入排序："); inputArray(array); }
折半插入排序
- 算法思想
基于直接插入排序，只是在确定插入位置时采用折半查找
-
实现
/** * 折半插入排序 * 跟直接插入相比只是在查找位置时，采用折半查找。 */ public static void halfInsert(int[] A) { int[] array = A; int len = array.length; for (int i = 1; i < len ; i++) { // 存放当前value的值 int value = array[i]; // 定义 low 和high 确定查找的范围 int low = 0; int high = i - 1; int middle; // 折半查找 while (low <= high) { middle = (low + high) / 2; if (array[middle] > value) { high = middle - 1; } else { low = middle + 1; } } //移位 for(int j = i - 1; j >= high + 1; j--){ array[j + 1] = array[j]; } array[high + 1] = value; } }
希尔排序（鸽一下下）
冒泡排序
-
算法思想
每轮从 i = 0 开始，确定一个最大的数或者最小的数
-
实现
/** * 冒泡排序 (从小到大) * 每一次都从 i = 0开始，与相邻的下一个元素开始比较，遇到比它小的交换位置，直到数组有序为止 * 第一个for 循环控制一共需要比较几轮 len - 1 * 第二个for 循环控制每次比较的次数 */ public static void bubble(int[] A) { int[] array = A; System.out.println("初始："); inputArray(array); int len = array.length; // 设置flag 当不发生交换时，证明数组已经有序，直接退出循环 for (int i = 1; i < array.length; i++) { boolean flag = true; for (int j = 0; j < len - i; j ++) { if (array[j] > array[j + 1]) { array[j] += array[j + 1]; array[j + 1] = array[j] - array[j + 1]; array[j] = array[j] - array[j + 1]; flag = false; } } if (flag) { break; } } System.out.println("冒泡排序:"); inputArray(array); }
快速排序
-
算法思想
每次选择一个数作为基数（一般都选第一个数），将所有比这个数大的放在这个数的右边，比它小的放左边
对新产生的两个序列分别按上诉方法再次拆分
-
对于 3 7 2 6 1 4 5 这个序列
-
选择第一个数 3 作为基数， 用两个指针实现把比基数大的移到右边，比基础小的移到左边。
-
(1)要先动 high指针，5 > 3 不用移动，所以 high–， 此时 4 > 3 high – , 1 < 3
就令 array[low] = array[high] （low 此时在 0 处）跳到2 -
(2)再动 low 指针，1 < 3 所以 low++， 7 >3 所以 令array[high] = array[low],返回1
-
上诉过程就是 3 7 2 6 1 4 5 ——> 1 7 2 6 1 4 5 (low = 0， high = 4) ->
1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->1 2 2 6 7 4 5(low = 2, high = 2)
-
最后令array[low] = base;
/**
* 快速排序
* 每次选择一个数作为基数（一般都选第一个数），将所有比这个数大的放在这个数的右边，比它小的放左边
* 对新产生的两个序列分别按上诉方法再次拆分
*/
public static void quick(int[] array, int high, int low) {
if (low < high) {
int base = part(array, high, low);
quick(array, base - 1, low);
quick(array, high, base + 1);
}
}
/**
* 对于 3 7 2 6 1 4 5 这个序列
* 选择第一个数 3 作为基数， 用两个指针实现把比基数大的移到右边，比基础小的移到左边。
* (1)要先动 high指针，5 > 3 不用移动，所以 high--， 此时 4 > 3 high -- , 1 < 3
* 就令 array[low] = array[high] （low 此时在 0 处）跳到2
* (2)再动 low 指针，1 < 3 所以 low++， 7 >3 所以 令array[high] = array[low],返回1
* 上诉过程就是 3 7 2 6 1 4 5 ——> 1 7 2 6 1 4 5 (low = 0， high = 4) ->
* 1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->
* 1 2 2 6 7 4 5(low = 2, high = 2)
* 最后令array[low] = base;
*
*
*/
public static int part (int[] array, int high, int low) {
// 选择第一个数作为基准数并定义base存放
int base = array[low];
while (low < high) {
while (low < high && array[high] > base) {
high--;
} // 找到比 base 小的数退出循环，再进行赋值
array[low] = array[high];
while (low < high && array[low] < base) {
low++;
}
array[high] = array[low];
}
array[high] = base;
return high;
}
简单选择排序
-
算法思想
每次选择一个最小的元素，然后与原位置上的元素进行交换
-
实现步骤
/** * 简单选择排序(从小到大) * 每次选择一个最小的元素，然后与原位置上的元素进行交换 */ public static void chooseSmiple(int[] array) { for (int i = 0; i < array.length; i++) { int min = array[i]; int key = i; for (int j = i; j < array.length; j++) { if (min > array[j]) { min = array[j]; key = j; } } // 交换 array[key] = array[i]; array[i] = min; } } }
堆排序（占个位）
归并排序 （占个位）
整体代码
import javax.xml.bind.annotation.XmlInlineBinaryData;
/**
* @author HelloWorld
* @create 2021-04-07-20:38
* @email 154803771@qq.com
*/
public class sort {
/**
* 排序算法
* 全部按照从小到大的顺序排序
*/
public static void main(String[] args) {
int[] array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
// 直接插入排序
insertDirectly(array);
System.out.println();
//折半插入排序
array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
System.out.println("初始时：");
inputArray(array);
halfInsert(array);
System.out.println("折半插入排序");
inputArray(array);
System.out.println();
//冒泡排序
array = new int[]{4, 7, 6, 2, 1, 5, 3, 9, 8};
bubble(array);
System.out.println();
//快速排序
array = new int[]{4, 7, 8, 9, 1, 5, 3, 2, 6};
System.out.println("初始时：");
inputArray(array);
quick(array, array.length - 1, 0);
System.out.println("快速排序后：");
inputArray(array);
System.out.println();
// 简单选择排序
array = new int[]{4, 7, 6, 2, 1, 5, 3, 9, 8};
System.out.println("初始时：");
inputArray(array);
chooseSmiple(array);
System.out.println("简单选择排序后：");
inputArray(array);
System.out.println();
}
public static void inputArray(int[] array) {
for (int data : array) {
System.out.print(data +" ");
}
System.out.println();
}
/**
* 直接插入排序（从小到大）
* 从第二位开始，依次向前比较，如果遇到比它大的移动位置
*/
public static void insertDirectly(int[] A) {
int[] array = A;
System.out.println("初始：");
inputArray(array);
int len = array.length;
for (int i = 1; i < len; i++) {
// 0 到 i - 1 这个序列一定是有序的，若 array[i] > array[i - 1] 此时的元素已经在它应在的位置上
// 所以只需要考虑当前元素在有序序列中的位置
for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
array[j] = array[j] ^ array[j - 1];
array[j - 1] = array[j] ^ array[j - 1];
array[j] = array[j] ^ array[j - 1];
}
}
System.out.println("直接插入排序：");
inputArray(array);
}
/**
* 折半插入排序
* 跟直接插入相比只是在查找位置时，采用折半查找。
*/
public static void halfInsert(int[] A) {
int[] array = A;
int len = array.length;
for (int i = 1; i < len ; i++) {
// 存放当前value的值
int value = array[i];
// 定义 low 和high 确定查找的范围
int low = 0;
int high = i - 1;
int middle;
// 折半查找
while (low <= high) {
middle = (low + high) / 2;
if (array[middle] > value) {
high = middle - 1;
} else {
low = middle + 1;
}
}
//移位
for(int j = i - 1; j >= high + 1; j--){
array[j + 1] = array[j];
}
array[high + 1] = value;
}
}
/**
* 冒泡排序 (从小到大)
* 每一次都从 i = 0开始，与相邻的下一个元素开始比较，遇到比它小的交换位置，直到数组有序为止
* 第一个for 循环控制一共需要比较几轮 len - 1
* 第二个for 循环控制每次比较的次数
*/
public static void bubble(int[] A) {
int[] array = A;
System.out.println("初始：");
inputArray(array);
int len = array.length;
// 设置flag 当不发生交换时，证明数组已经有序，直接退出循环
for (int i = 1; i < array.length; i++) {
boolean flag = true;
for (int j = 0; j < len - i; j ++) {
if (array[j] > array[j + 1]) {
array[j] += array[j + 1];
array[j + 1] = array[j] - array[j + 1];
array[j] = array[j] - array[j + 1];
flag = false;
}
}
if (flag) {
break;
}
}
System.out.println("冒泡排序:");
inputArray(array);
}
/**
* 快速排序
* 每次选择一个数作为基数（一般都选第一个数），将所有比这个数大的放在这个数的右边，比它小的放左边
* 对新产生的两个序列分别按上诉方法再次拆分
*/
public static void quick(int[] array, int high, int low) {
if (low < high) {
int base = part(array, high, low);
quick(array, base - 1, low);
quick(array, high, base + 1);
}
}
/**
* 对于 3 7 2 6 1 4 5 这个序列
* 选择第一个数 3 作为基数， 用两个指针实现把比基数大的移到右边，比基础小的移到左边。
* (1)要先动 high指针，5 > 3 不用移动，所以 high--， 此时 4 > 3 high -- , 1 < 3
*就令 array[low] = array[high] （low 此时在 0 处）跳到2
* (2)再动 low 指针，1 < 3 所以 low++， 7 >3 所以 令array[high] = array[low],返回1
* 上诉过程就是 3 7 2 6 1 4 5 ——> 1 7 2 6 1 4 5 (low = 0， high = 4) ->
* 1 7 2 6 7 4 5(low = 1 high = 4) -> 1 2 2 6 7 4 5 (low = 1, high = 2) ->
* 1 2 2 6 7 4 5(low = 2, high = 2)
* 最后令array[low] = base;
*
*
*/
public static int part (int[] array, int high, int low) {
// 选择第一个数作为基准数并定义base存放
int base = array[low];
while (low < high) {
while (low < high && array[high] > base) {
high--;
} // 找到比 base 小的数退出循环，再进行赋值
array[low] = array[high];
while (low < high && array[low] < base) {
low++;
}
array[high] = array[low];
}
array[high] = base;
return high;
}
/**
* 简单选择排序(从小到大)
* 每次选择一个最小的元素，然后与原位置上的元素进行交换
*/
public static void chooseSmiple(int[] array) {
for (int i = 0; i < array.length; i++) {
int min = array[i];
int key = i;
for (int j = i; j < array.length; j++) {
if (min > array[j]) {
min = array[j];
key = j;
}
}
// 交换
array[key] = array[i];
array[i] = min;
}
}
}
这篇关于排序算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
-
Java项目部署入门：新手必看指南11-23
-
Java项目部署入门：新手必读指南11-23
-
Java项目开发入门：新手必读指南11-23
-
JAVA项目开发入门：从零开始的实用教程11-23
栏目导航
