java实现的各种排序算法代码示例
发布时间：2020-12-14 21:20:53 所属栏目：Java 来源：网络整理
导读：折半插入排序 折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的 插入位置，这实际上是一种查找算法：折半查找。Java的Arrays类里的binarySearch()方法，就是折半查找的实现，用 于从指定数组中查
|
折半插入排序 折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入，其实就是通过不断地折半来快速确定第i个元素的 代码：
package interview;
/**
* @author Administrator
* 折半插入排序
*/
public class BinaryInsertSort {
public static void binaryInsertSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {
DataWrap temp = data[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (temp.compareTo(data[mid]) > 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
for (int j = i; j > low; j--) {
data[j] = data[j - 1];
}
data[low] = temp;
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,""),new DataWrap(-16,new DataWrap(21,"*"),new DataWrap(23,new DataWrap(-30,new DataWrap(-49,new DataWrap(30,"")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果： 排序之前： [9,-16,21*,23,-30,-49,21,30*,30] 开始排序 [-16,9,30] [-16,30] [-30,30] [-49,30,30*] 排序之后： [-49,30*] 冒泡排序 代码：
package interview;
/**
* @author Administrator
* 冒泡排序
*/
public class BubbleSort {
public static void bubbleSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLength - 1 - i; j++) {
if (data[j].compareTo(data[j + 1]) > 0) {
DataWrap temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
flag = true;
}
}
System.out.println(java.util.Arrays.toString(data));
if (!flag)
break;
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
运行结果： 排序之前： [9,30] 排序之后： [-49,30] 桶式排序 算法的时间效率：时间效率极高，只需经过两轮遍历即可算法的空间效率：空间开销较大，需要两个数组来完成，算
package interview;
import java.util.Arrays;
/**
* @author Administrator
* 桶式排序
*/
public class BucketSort {
public static void bucketSort(DataWrap[] data,int min,int max) {
System.out.println("开始排序");
int arrayLength = data.length;
DataWrap[] temp = new DataWrap[arrayLength];
int[] buckets = new int[max - min];
for (int i = 0; i < arrayLength; i++) {
buckets[data[i].data - min]++;
}
System.out.println(Arrays.toString(buckets));
for (int i = 1; i < max - min; i++) {
buckets[i] = buckets[i] + buckets[i - 1];
}
System.out.println(Arrays.toString(buckets));
System.arraycopy(data,temp,arrayLength);
for (int k = arrayLength - 1; k >= 0; k--) {
data[--buckets[temp[k].data - min]] = temp[k];
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,new DataWrap(5,new DataWrap(-1,new DataWrap(8,new DataWrap(7,new DataWrap(3,new DataWrap(-3,new DataWrap(1,"*")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
bucketSort(data,-3,10);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果 排序之前： [9,5,-1,8,5*,7,3,1,3*] 开始排序 [1,2,1] [1,10] 排序之后： [-3,3*,9] 堆排序 代码：
package interview;
/**
* @author Administrator
* 堆排序
*/
public class HeapSort {
public static void heapSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
// 循环建堆
for (int i = 0; i < arrayLength - 1; i++) {
// 建堆
builMaxdHeap(data,arrayLength - 1 - i);
// 交换堆顶和最后一个元素
swap(data,arrayLength - 1 - i);
System.out.println(java.util.Arrays.toString(data));
}
}
// 对data数组从0到lastIndex建大顶堆
private static void builMaxdHeap(DataWrap[] data,int lastIndex) {
// 从lastIndex处节点（最后一个节点）的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// k保存当前正在判断的节点
int k = i;
// 如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
// k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
// 如果biggerIndex小于lastIndex，即biggerIndex +1
// 代表k节点的右子节点存在
if (biggerIndex < lastIndex) {
// 如果右子节点的值较大
if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
// biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
// 如果k节点的值小于其较大子节点的值
if (data[k].compareTo(data[biggerIndex]) < 0) {
// 交换它们
swap(data,k,biggerIndex);
// 将biggerIndex赋给k，开始while循环的下一次循环
// 重新保证k节点的值大于其左、右节点的值
k = biggerIndex;
} else {
break;
}
}
}
}
// 交换data数组中i、j两个索引处的元素
private static void swap(DataWrap[] data,int i,int j) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
heapSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果： 排序之前： [9,30*] [-16,30*] [21,30*] [-49,30*] [-30,30*] 直接插入排序
package interview;
public class InsertSort {
public static void insertSort(DataWrap[] data){
System.out.println("开始排序");
int arrayLength = data.length;
for(int i = 1;i < arrayLength;i++){
DataWrap temp = data[i];
if(data[i].compareTo(data[i-1]) < 0){
int j = i -1;
for(;j >= 0 && data[j].compareTo(temp) > 0;j--){
data[j +1] = data[j];
}
data[j + 1] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
insertSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果 排序之前： [9,30] 归并排序 算法的时间效率：归并算法需要递归地进行分解、合并，每进行一趟归并排序，需要merge()方法一次，每次执行
package interview;
/**
* @author Administrator
* 归并排序
*/
public class MergeSort {
public static void mergeSort(DataWrap[] data) {
// 归并排序
sort(data,data.length - 1);
}
// 将索引从left到right范围的数组元素进行归并排序
private static void sort(DataWrap[] data,int left,int right) {
if(left < right){
//找出中间索引
int center = (left + right)/2;
sort(data,left,center);
sort(data,center+1,right);
//合并
merge(data,center,right);
}
}
// 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序
private static void merge(DataWrap[] data,int center,int right) {
DataWrap[] tempArr = new DataWrap[data.length];
int mid = center + 1;
int third = left;
int temp = left;
while (left <= center && mid <= right) {
if (data[left].compareTo(data[mid]) <= 0) {
tempArr[third++] = data[left++];
} else {
tempArr[third++] = data[mid++];
}
}
while (mid <= right) {
tempArr[third++] = data[mid++];
}
while (left <= center) {
tempArr[third++] = data[left++];
}
while (temp <= right) {
data[temp] = tempArr[temp++];
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"") };
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
mergeSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果： 排序之前： [9,30] 基数排序 基数排序已经不再是一种常规的排序方法，它更多地像是一种排序方法的应用，基数排序必须依赖于另外的排序方法。 最高位优先法MSD 比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简单，因为LSD法是从头到尾进行若干次分配和收集，执行 代码：
package interview;
import java.util.Arrays;
/**
* @author Administrator
* 基数排序
*/
public class MultiKeyRadixSort {
public static void radixSort(int[] data,int radix,int d) {
System.out.println("开始排序：");
int arrayLength = data.length;
int[] temp = new int[arrayLength];
int[] buckets = new int[radix];
for (int i = 0,rate = 1; i < d; i++) {
// 重置count数组，开始统计第二个关键字
Arrays.fill(buckets,0);
// 当data数组的元素复制到temp数组中进行缓存
System.arraycopy(data,arrayLength);
for (int j = 0; j < arrayLength; j++) {
int subKey = (temp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
for (int m = arrayLength - 1; m >= 0; m--) {
int subKey = (temp[m] / rate) % radix;
data[--buckets[subKey]] = temp[m];
}
System.out.println("对" + rate + "位上子关键字排序："
+ java.util.Arrays.toString(data));
rate *= radix;
}
}
public static void main(String[] args) {
int[] data = { 1100,192,221,12,13 };
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
radixSort(data,10,4);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果 排序之前： [1100,13] 开始排序： 对1位上子关键字排序：[1100,13] 对10位上子关键字排序：[1100,13,192] 对100位上子关键字排序：[12,1100,221] 对1000位上子关键字排序：[12,1100] 排序之后： [12,1100] 快速排序 代码：
package interview;
/**
* @author Administrator
* 快速排序
*/
public class QuickSort {
private static void swap(DataWrap[] data,int j) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(DataWrap[] data,int start,int end) {
if (start < end) {
DataWrap base = data[start];
int i = start;
int j = end + 1;
while (true) {
while (i < end && data[++i].compareTo(base) <= 0)
;
while (j > start && data[--j].compareTo(base) >= 0)
;
if (i < j) {
swap(data,i,j);
} else {
break;
}
}
swap(data,start,j);
subSort(data,j - 1);
subSort(data,j + 1,end);
}
}
public static void quickSort(DataWrap[] data){
subSort(data,data.length-1);
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"") };
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果 排序之前： [9,30] 直接选择排序 代码：
package interview;
/**
* @author Administrator
* 直接选择排序
*/
public class SelectSort {
public static void selectSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
for (int j = i + 1; j < arrayLength; j++) {
if (data[i].compareTo(data[j]) > 0) {
DataWrap temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
System.out.println(java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9,"") };
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
selectSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
排序之前： [9,30] 开始排序 [-49,30] 希尔排序 代码：
package interview;
/**
* @author Administrator
* Shell排序
*/
public class ShellSort {
public static void ShellSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
int h = 1;
/**
* 将数组分割成若干个子序列
*/
while (h <= arrayLength / 3) {
h = h * 3 + 1;
System.out.println("h的结果：" + h);
}
while (h > 0) {
System.out.println("===h的值：" + h + "===");
/**
* 将分成的若干子序列进行直接插入排序
*/
for (int i = h; i < arrayLength; i++) {
DataWrap temp = data[i];
if (data[i].compareTo(data[i - h]) < 0) {
int j = i - h;
for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) {
data[j + h] = data[j];
}
data[j + h] = temp;
}
System.out.println(java.util.Arrays.toString(data));
}
h = (h - 1) / 3;
}
}
public static void main(String[] args) {
DataWrap[] data = {
new DataWrap(9,"")};
System.out.println("排序之前：n" + java.util.Arrays.toString(data));
ShellSort(data);
System.out.println("排序之后：n" + java.util.Arrays.toString(data));
}
}
结果： 排序之前： [9,30] 开始排序 h的结果：4 ===h的值：4=== [-30,30] ===h的值：1=== [-49,30] 所需要的工具类：
package interview;
public class DataWrap implements Comparable<DataWrap>{
int data;
String flag;
public DataWrap(int data,String flag) {
this.data = data;
this.flag = flag;
}
public String toString(){
return data + flag;
}
@Override
public int compareTo(DataWrap dw) {
return this.data > dw.data ?
1 : (this.data == dw.data ? 0 : -1);
}
}
以上代码亲测可用，供大家参考。 关于java实现的各种排序算法代码示例的内容，就到这里，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：Java 蒙特卡洛算法求圆周率近似值实例详解、Java编程实现递增排序链表的合并、Java编程ssh整合常见错误解析等，有什么问题可以随时留言，小编会及时回复大家的。这里推荐本站几本关于Java的书籍，免费下载，供广大编程爱好及工作者参考。 Java经典实例(第三版) 完整版 ([美]达尔文) 中文pdf扫描版 http://www.aspzz.cn/books/577859.html 数据挖掘：实用机器学习技术及Java实现（英文第2版）高清PDF www.aspzz.cn/books/577815.html Java初级开发工程师面试题汇总.PDF http://www.aspzz.cn/books/576989.html 希望大家能够喜欢。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |