溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Java中八大排序算法是什么，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
基本思想：
將新的數(shù)據(jù)插入已經(jīng)排好的數(shù)據(jù)列中。
將第一個和第二個數(shù)排序，構成有序數(shù)列
然后將第三個數(shù)插進去，構成新的有序數(shù)列，后面的數(shù)重復這個步驟
算法描述
1、設定插入的次數(shù)，即是循環(huán)次數(shù),for(int i=1;i<length;i++)，1個數(shù)的那次不用插入。
2、設定插入的數(shù)和得到的已經(jīng)排好的序列的最后一個數(shù),insertNum和j=i-1。
3、從最后一個數(shù)向前開始循環(huán)，如果插入數(shù)小于當前數(shù)就將當前數(shù)向前移動一位
4、將當前位置放置到空的位置，即j+1。
代碼實現(xiàn)
public class Demo01 {
public static void main(String[] args) {
int [] data = {2,1,41,21,14,33,5};
int temp; //要插入的數(shù)
for (int i = 1; i < data.length; i++) { // 插入的次數(shù)
temp = data[i]; //要插入的數(shù)
int j = i-1; //已經(jīng)排好的數(shù)字
while (j>=0&&data[j]>temp){ //判斷后一個數(shù)，將大于要插入的數(shù)向后移動一格
data[j+1] =data[j]; //元素移動一格
j--;
}
data[j+1]=temp; //將要插入的數(shù)字放入1插入的位置
}
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]+" ");
}
}
}基本思想：
對于直接插入的數(shù)，數(shù)據(jù)量巨大：
1.將數(shù)的個數(shù)設置為n，取奇數(shù)k = n/2,將下標的差值k的數(shù)分為一組，構成有序數(shù)列。
2.再取k = k/2,將下標差值為k的數(shù)構成一組，構成有序數(shù)列，
3.重復第二步，直到k=1執(zhí)行簡單的插入排序
算法描述
1.首先確定分組的數(shù)字
2.然后對組中的數(shù)字進行插入排序
3.然后將length/2，重復1,2步驟。直到length=0為止。
代碼實現(xiàn)
public class Demo02 {
public static void main(String[] args) {
int [] data = {2,5,14,34,12,4,87,21,1,6};
int d = data.length;
while (d!=0){
d = d/2;
for (int x = 0; x < d; x++) {
for (int i = d+x; i < data.length; i += d) {
int j = i - d; //j為有序序列最后一位的位數(shù)
int temp = data[i]; //要插入的元素
for (;j>=0&&temp < data[j]; j -=d){
data[j+d]=data[j]; //向后移動d位
}
data[j+d] = temp;
}
}
}
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]+" ");
}
}
}基本思想：
常用于取序列數(shù)中最大最小的幾棵樹
(如果每次比較都交換，那么就是交換排序；如果每次比較完一個循環(huán)再交換，就是簡單選擇排序。)
1.遍歷整個序列，將最小的數(shù)放在最前面
2.遍歷剩余的序列，將最小的數(shù)字放在最前面
3.重復步驟2，知道剩余最后一個數(shù)字。
算法描述
1.首先確定循環(huán)次數(shù)，并且記住當前的位置和當前數(shù)字
2.將當前位置后面的所有數(shù)字和當前位置的數(shù)字作比較，小數(shù)賦值給key,并記住小值的位置
3.比對完成后，將最小的值和第一個數(shù)的值交換
4.重復2,3步驟
代碼實現(xiàn)
public class Demo03 {
public static void main(String[] args) {
int[] data = {2,6,123,56,23,1};
for (int i = 0; i < data.length; i++) { //循環(huán)次數(shù)
int key = data[i];//最小值
int position=i; //當前位置
for (int j = i+1; j < data.length; j++) {//選出最小值
if(data[j]<key){
key = data[j];
position =j;
}
}
data[position] = data[i];//交換位置
data[i] = key;
}
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]+" ");
}
}
}基本思想：
對簡單選擇排序的優(yōu)化
1.將序列構建為大頂堆
2.將根節(jié)點與最后一個節(jié)點兌換，然后斷開最后一個節(jié)點
3.重復一二步驟，直到所有節(jié)點斷開
代碼實現(xiàn)：
public class Demo04 {
public static void main(String[] args) {
int []data = {21,13,3,2,1,23,11,25};
heapsort(data);
}
public static void heapsort(int a[]){
System.out.println("開始排序");
int arrayLength = a.length;
for (int i = 0; i < arrayLength-1; i++) {
buildMaxHeap(a,arrayLength-1-i);
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
private static void swap(int[] data, int i, int j) {
// TODO Auto-generated method stub
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
public static void buildMaxHeap(int[] data,int lastIndex){
//從lastIndex處節(jié)點（最后一個節(jié)點）的父節(jié)點開始
for (int i = (lastIndex-1)/2;i>=0;i--){
//k 保存當前判斷的節(jié)點
int k = i;
// 如果當前k節(jié)點存在子節(jié)點
while (k*2+1<=lastIndex){
// k節(jié)點的左子節(jié)點的索引
int biggerIndex = 2*k+1;
// 如果biggerIndex小于lastIndex，即biggerIndex+1代表的k節(jié)點的右子節(jié)點存在
if (biggerIndex<lastIndex){
// 如果右子節(jié)點的值較大
if(data[biggerIndex]<data[biggerIndex+1]){
biggerIndex++;
}
}
// 如果k節(jié)點的值小于其較大的子節(jié)點的值
if (data[k]<data[biggerIndex]){
swap(data,k,biggerIndex);
k = biggerIndex;
}else {
break;
}
}
}
}
}基本思想
1.將序列中所有的元素兩兩比較
2.將剩余序列的所有元素兩兩比較，將最大的放到最后面
3.重復第二步，知道最后一個數(shù)
算法描述
1.設置循環(huán)次數(shù)
2.設置比較的位數(shù)和結束的位數(shù)
3.兩兩比較，將最小的放到前面去
4.重復2，3步驟，直到循環(huán)結束
代碼實現(xiàn)
public class Demo05 {
public static void main(String[] args) {
int[] data={1,34,31,2,65,87,255,8,33,64,3};
int temp;
for (int i = 0; i < data.length; i++) {
for (int j = 0; j < data.length-i-1; j++) {
if(data[j] > data[j+1]){
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for (int i = 0; i < data.length; i++) {
System.out.print(data[i]+" ");
}
}
}基本思想
要求時間最快
1.選擇第一個數(shù)作為P,小于P的放左邊，大于p的放右邊
2.遞歸將p的左邊和右邊的數(shù)按照步驟一進行，直到不能遞歸
代碼實現(xiàn)
public class Demo06 {
public static void main(String[] args) {
int[] data = {5,33,22,11,23,2,32,12,21,10};
quickSort(data,0,data.length-1);
sorts(data);
}
public static void quickSort(int[] data,int L,int R){
if(L < R){
// 先選擇比較的基數(shù)
int base = data[L];
int temp;
int left=L,right=R;
do{
while ((data[left] < base) && (left < R)){
left++;
}
while ((data[right]) > base &&(right > L)){
right--;
}
if (left <= right){
temp = data[left];
data[left] = data[right];
data[right] = temp;
left++;
right--;
}
}while (left <= right);
if (L < right){
quickSort(data,L,right);
}
if (R > left){
quickSort(data,left,R);
}
}
}
public static void sorts(int[] data){
for (int i = 0; i < data.length; i++) {
if (i == data.length-1){
System.out.print(data[i]);
}else {
System.out.print(data[i]+",");
}
}
}
}基本思想
速度僅次于快排，內(nèi)存少的時候使用，可以進行并行運算的時候使用。
1.選擇相鄰兩個數(shù)組成的有序序列
2.選擇相鄰的兩個有序序列組成的一個有序序列
3.重復步驟二，直到組成一個有序序列
public class Demo0701 {
public static void main(String[] args) {
int[] arr = {12,34,3,2,13,43,34,25,83};
mSort(arr, 0, arr.length-1);
sorts(arr);
}
/**
* 遞歸分治
* @param arr 待排數(shù)組
* @param left 左指針
* @param right 右指針
*/
public static void mSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int mid = (left + right) / 2;
mSort(arr, left, mid); //遞歸排序左邊
mSort(arr, mid+1, right); //遞歸排序右邊
merge(arr, left, mid, right); //合并
}
/**
* 合并兩個有序數(shù)組
* @param arr 待合并數(shù)組
* @param left 左指針
* @param mid 中間指針
* @param right 右指針
*/
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] temp = new int[right - left + 1]; //中間數(shù)組
int i = left;
int j = mid + 1;
int k = 0;
//執(zhí)行完這個while循環(huán)，相當于將兩個子序列合并后重新進行了一次排序并將排序結果記錄在了臨時數(shù)組temp[k]中。
// while走完后k的值等于數(shù)組的長度，i的值此時大于mid，j的值大于right
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while(i <= mid) {
temp[k++] = arr[i++];
}
while(j <= right) {
temp[k++] = arr[j++];
}
//將有序的臨時數(shù)組temp[k]一個一個賦值到原數(shù)組arr[]中
for(int p=0; p<temp.length; p++) {
arr[left + p] = temp[p];
}
}
public static void sorts(int[] data){
for (int i = 0; i < data.length; i++) {
if (i == data.length-1){
System.out.print(data[i]);
}else {
System.out.print(data[i]+",");
}
}
}
}基本思想
用于大量數(shù)，很長數(shù)進行排列
1.將所有的數(shù)的個數(shù)取出來，按照個位數(shù)排序，構成序列
2.將新構成的所有數(shù)的十位數(shù)取出，按照十位數(shù)進行排序
代碼實現(xiàn)
public class Demo08 {
public static void main(String[] args) {
int[] data = {12,34,3,2,13,43,34,25,83};
if(data == null && data.length == 0)
return ;
int maxBit = getMaxBit(data);
for(int i=1; i<=maxBit; i++) {
List<List<Integer>> buf = distribute(data, i); //分配
collecte(data, buf); //收集
}
new PrintSort(data);
}
/**
* 分配
* @param arr 待分配數(shù)組
* @param iBit 要分配第幾位
* @return
*/
public static List<List<Integer>> distribute(int[] arr, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for(int j=0; j<10; j++) {
buf.add(new LinkedList<Integer>());
}
for(int i=0; i<arr.length; i++) {
buf.get(getNBit(arr[i], iBit)).add(arr[i]);
}
return buf;
}
/**
* 收集
* @param arr 把分配的數(shù)據(jù)收集到arr中
* @param buf
*/
public static void collecte(int[] arr, List<List<Integer>> buf) {
int k = 0;
for(List<Integer> bucket : buf) {
for(int ele : bucket) {
arr[k++] = ele;
}
}
}
/**
* 獲取最大位數(shù)
* @param
* @return
*/
public static int getMaxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for(int ele : arr) {
int len = (ele+"").length();
if(len > max)
max = len;
}
return max;
}
/**
* 獲取x的第n位，如果沒有則為0.
* @param x
* @param n
* @return
*/
public static int getNBit(int x, int n) {
String sx = x + "";
if(sx.length() < n)
return 0;
else
return sx.charAt(sx.length()-n) - '0';
}
}關于“Java中八大排序算法是什么”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
