java实现的各种排序算法


折半插入排序

折半插入排序是对直接插入排序的简单改进。此处介绍的折半插入,其实就是通过不断地折半来快速肯定第i个元素的

插入位置,这实际上是1种查找算法:折半查找。Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用

于从指定数组中查找指定元素,条件是该数组已处于有序状态。与直接插入排序的效果相同,只是更快了1些,因

为折半插入排序可以更快地肯定第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(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
binaryInsertSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

冒泡排序

代码

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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

桶式排序

算法的时间效力:时间效力极高,只需经过两轮遍历便可算法的空间效力:空间开消较大,需要两个数组来完成,算
法的稳定性:稳定
代码:

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, 0, temp, 0, 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(⑴, ""), new DataWrap(8, ""),
new DataWrap(5, "*"), new DataWrap(7, ""),
new DataWrap(3, ""), new DataWrap(⑶, ""),
new DataWrap(1, ""),new DataWrap(3, "*")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
bucketSort(data, ⑶, 10);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

堆排序

代码:
<span style="font-size:18px;">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);
// 交换堆顶和最后1个元素
swap(data, 0, arrayLength – 1 – i);
System.out.println(java.util.Arrays.toString(data));
}
}

// 对data数组从0到lastIndex建大顶堆
private static void builMaxdHeap(DataWrap[] data, int lastIndex) {
// 从lastIndex处节点(最后1个节点)的父节点开始
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循环的下1次循环
// 重新保证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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
heapSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

直接插入排序

package interview;

* @author Administrator
* 直接插入排序
*/
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⑴]) < 0){
int j = i ⑴;
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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
insertSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}


归并排序

算法的时间效力:归并算法需要递归地进行分解、合并,每进行1趟归并排序,需要merge()方法1次,每次履行
merge()需要比较n次,较差,需要1个与原始序列一样大小的辅助序列。算法的稳定性:稳定
代码:

package interview;

/**
* @author Administrator
* 归并排序
*/
public class MergeSort {
public static void mergeSort(DataWrap[] data) {
// 归并排序
sort(data, 0, 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,left,center,right);
}
}

// 将两个数组进行归并,归并前两个数组已有序,归并后仍然有序
private static void merge(DataWrap[] data, int left, 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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
mergeSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

基数排序

基数排序已不再是1种常规的排序方法,它更多地像是1种排序方法的利用,基数排序必须依赖于另外的排序方法。
基数排序的整体思路就是将待排数据拆分成多个关键字进行排序,也就是说,基数排序的实质是多关键字排序。
多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字:第1个子关键字、第2个子关键字、第3个子
关键字。。。然后,根据子关键字对待排数据进行排序。在进行多关键字排序时有两种解决方案:
最高位优先法MSD
最低位优先法LSD
比较MSD法和LSD法,1般来说,LSD法要比MSD法来得简单,由于LSD法是从头到尾进行若干次分配和搜集,履行
的次数取决于构成关键字值的成份为多少;而MSD法则要处理各序列与子序列的独立排序问题,便可能复杂1些。


代码:

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数组,开始统计第2个关键字
Arrays.fill(buckets, 0);
// 当data数组的元素复制到temp数组中进行缓存
System.arraycopy(data, 0, temp, 0, 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));
}
}

快速排序

代码:

package interview;

/**
* @author Administrator
* 快速排序
*/
public class QuickSort {
private static void swap(DataWrap[] data, int i, 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, start, j – 1);
subSort(data, j + 1, end);
}
}
public static void quickSort(DataWrap[] data){
subSort(data,0,data.length⑴);
}
public static void main(String[] args) {
DataWrap[] data = { new DataWrap(9, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

直接选择排序

代码:

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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "") };
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
selectSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

希尔排序

代码:

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, ""), new DataWrap(⑴6, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(⑶0, ""), new DataWrap(⑷9, ""),
new DataWrap(21, ""), new DataWrap(30, "*"),
new DataWrap(30, "")};
System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
ShellSort(data);
System.out.println("排序以后:\n" + java.util.Arrays.toString(data));
}
}

所需要的工具类

package interview;

//定义1个数据包装类
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 : ⑴);
}

}





波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » java实现的各种排序算法

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡