溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
折半插入排序
折半插入排序是對直接插入排序的簡單改進。此處介紹的折半插入，其實就是通過不斷地折半來快速確定第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(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));
}
}
結果：
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-30, -16, 9, 21*, 23, -49, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30*, 30] [-49, -30, -16, 9, 21, 21*, 23, 30, 30*] 排序之后： [-49, -30, -16, 9, 21, 21*, 23, 30, 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, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
運行結果：
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 [-16, 9, 21*, -30, -49, 21, 23, 30*, 30] [-16, 9, -30, -49, 21*, 21, 23, 30*, 30] [-16, -30, -49, 9, 21*, 21, 23, 30*, 30] [-30, -49, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 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, 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(-1, ""), new DataWrap(8, ""),
new DataWrap(5, "*"), new DataWrap(7, ""),
new DataWrap(3, ""), new DataWrap(-3, ""),
new DataWrap(1, ""),new DataWrap(3, "*")};
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, -3, 1, 3*] 開始排序 [1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1] [1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10] 排序之后： [-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 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, 0, 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, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
結果：
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 [-16, 30, 21*, 23, -30, -49, 21, 9, 30*] [-16, 23, 21*, 9, -30, -49, 21, 30, 30*] [21, 9, 21*, -16, -30, -49, 23, 30, 30*] [-49, 9, 21*, -16, -30, 21, 23, 30, 30*] [-30, 9, -49, -16, 21*, 21, 23, 30, 30*] [-30, -16, -49, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] [-49, -30, -16, 9, 21*, 21, 23, 30, 30*] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 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, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
結果
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-16, 9, 21*, 23, -30, -49, 21, 30*, 30] [-30, -16, 9, 21*, 23, -49, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
歸并排序
算法的時間效率：歸并算法需要遞歸地進行分解、合并，每進行一趟歸并排序，需要merge()方法一次，每次執行
merge()需要比較n次，較差，需要一個與原始序列同樣大小的輔助序列。算法的穩定性：穩定
代碼：
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(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
結果：
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
基數排序
基數排序已經不再是一種常規的排序方法，它更多地像是一種排序方法的應用，基數排序必須依賴于另外的排序方法。
基數排序的總體思路就是將待排數據拆分成多個關鍵字進行排序，也就是說，基數排序的實質是多關鍵字排序。
多關鍵字排序的思路是將待排數據里的排序關鍵字拆分成多個排序關鍵字：第1個子關鍵字、第2個子關鍵字、第3個子
關鍵字。。。然后，根據子關鍵字對待排數據進行排序。在進行多關鍵字排序時有兩種解決方案：
最高位優先法MSD
最低位優先法LSD
比較MSD法和LSD法，一般來講，LSD法要比MSD法來得簡單，因為LSD法是從頭到尾進行若干次分配和收集，執行
的次數取決于構成關鍵字值的成分為多少；而MSD法則要處理各序列與子序列的獨立排序問題，就可能復雜一些。
代碼：
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, 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));
}
}
結果
排序之前： [1100, 192, 221, 12, 13] 開始排序： 對1位上子關鍵字排序：[1100, 221, 192, 12, 13] 對10位上子關鍵字排序：[1100, 12, 13, 221, 192] 對100位上子關鍵字排序：[12, 13, 1100, 192, 221] 對1000位上子關鍵字排序：[12, 13, 192, 221, 1100] 排序之后： [12, 13, 192, 221, 1100]
快速排序
代碼：
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-1);
}
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(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));
}
}
結果
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 排序之后： [-49, -30, -16, 9, 21, 21*, 23, 30*, 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, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 [-49, 9, 21*, 23, -16, -30, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, -16, 23, 21*, 9, 21, 30*, 30] [-49, -30, -16, 9, 23, 21*, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 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, ""), new DataWrap(-16, ""),
new DataWrap(21, "*"), new DataWrap(23, ""),
new DataWrap(-30, ""), new DataWrap(-49, ""),
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));
}
}
結果：
排序之前： [9, -16, 21*, 23, -30, -49, 21, 30*, 30] 開始排序 h的結果：4 ===h的值：4=== [-30, -16, 21*, 23, 9, -49, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] [-30, -49, 21*, 23, 9, -16, 21, 30*, 30] ===h的值：1=== [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 21*, 23, 9, -16, 21, 30*, 30] [-49, -30, 9, 21*, 23, -16, 21, 30*, 30] [-49, -30, -16, 9, 21*, 23, 21, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] [-49, -30, -16, 9, 21*, 21, 23, 30*, 30] 排序之后： [-49, -30, -16, 9, 21*, 21, 23, 30*, 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掃描版
https://www.jb51.net/books/577859.html
數據挖掘：實用機器學習技術及Java實現（英文第2版）高清PDF
www.jb51.net/books/577815.html
Java初級開發工程師面試題匯總.PDF
https://www.jb51.net/books/576989.html
希望大家能夠喜歡。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
