java排序算法代码_Java实现八种排序算法（代码详细解释）
package八大排序算法;importjava.util.Arrays;importorg.junit.Test;/*** 1、插入排序 直接插入排序、希爾排序 折半插入排序
* 2、交換排序 冒泡排序、快速排序
* 3、選擇排序 直接選擇排序、堆排序
* 4、歸并排序
* 5、分配排序 基數(shù)排序 箱排序
*
*
*
* 八大排序算法。
*
*
*@author劉陽(yáng)陽(yáng)
*
* 2017年2月25日*/
public classInsertSort {//此類用到的排序數(shù)組
int[] a = { 0, 9, 5, 6, 12, 31, 23, 15, 100};//int[] b = {0,9,5,6,12,31,23,15,100};
/*** * ==============================================================
* 1、插入排序之->直接插入排序
* 特點(diǎn)：
* 1、穩(wěn)定排序
* 2、算法簡(jiǎn)便，且容易實(shí)現(xiàn) 3、可適用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
* 4、更適合于初始記錄基本有序(正序)，當(dāng)初始記錄無序，n較大時(shí)，此算法時(shí)間復(fù)雜度較高，不宜采用。
* ================================================================*/@Testpublic voidIInsertSort() {
System.out.println("1、插入排序之->直接插入排序");int j = 0;for (int i = 2; i < a.length; i++) { //此處i=2，是因?yàn)橹苯硬迦肱判蚰J(rèn)1為拍好的序列，i！=0//是因?yàn)轭A(yù)留0的空間來暫存每次的結(jié)果
if (a[i] < a[i - 1]) {//當(dāng)a[i] < a[i-1]時(shí)才需要操作，否則因?yàn)楸緛砭褪呛玫男蛄?#xff0c;直接跳過
a[0] =a[i];
a[i]= a[i - 1];//開始挪窩
for (j = i - 2; a[0] < a[j]; j--) { //j=i-2 為什么-2//是因?yàn)?2之后當(dāng)前就是從后往前遍歷了，-》a[i]//= a[i-1] 與 j=i-2 是本題一個(gè)關(guān)鍵
a[j + 1] =a[j];
}
a[j+ 1] = a[0];
}
}
print(a);
}/*** * ====================================== 1、插入排序之->折半插入排序 特點(diǎn)： 1、穩(wěn)定排序
* 2、因?yàn)橐M(jìn)行折半查找，所以只能用于順序結(jié)構(gòu)，不能用于鏈?zhǔn)浇Y(jié)構(gòu) 3、適合初始記錄無序，且n較大的情況
* ======================================*/@Testpublic voidBInsertSort() {intlow;intheight;intj;intm;for (int i = 2; i < a.length; i++) { //i=2,代表從2開始
a[0] = a[i];//先把當(dāng)前值存到a[0]
low = 1;
height= i - 1; //給low和height賦值，low從1開始，height從比 當(dāng)前值i小1，開始
while (low <= height) { //一直循環(huán)的條件是 low<=height,在這之后的第3行的 height =//m-1，可以改變結(jié)束循環(huán)的條件。
m = (low + height) / 2; //首先算出來m;
if (a[0] < a[m]) { //如果a[0]
height = m - 1; //所有把中間m-1點(diǎn)復(fù)制給height，為何是m-1，因?yàn)閙已經(jīng)用過了，所有是m-1;
} else{
low= m + 1; //否則代表 插入點(diǎn)后半段，則把m+1復(fù)制給low，來繼續(xù)去搜索后半段
}
}//開始挪窩
for (j = i - 1; j >= height + 1; j--) { //和直接插入排序相比，此處j=j-1//還是從后往前遍歷
a[j + 1] = a[j]; //把當(dāng)前j給j+1
}
a[j+ 1] = a[0]; //最后把a(bǔ)[0]給j+1，因?yàn)閖是全局變量，所以j的值會(huì)隨著開始挪窩循環(huán)的變化減小，直至見到最佳
}
System.out.println("1、插入排序之->折半插入排序");
print(a);
}/***
* ======================================
* 1、插入排序之->希爾排序方法一
* 特點(diǎn)：
* 1、記錄跳躍式移動(dòng)導(dǎo)致排序方法是不穩(wěn)定的
* 2、只能用于順序結(jié)構(gòu)，不能用于鏈?zhǔn)浇Y(jié)構(gòu)
* 3、綜合來說，n越大，效果越明顯，所以適合初始記錄無序，n較大時(shí)的情況~。
* ======================================*/@Testpublic voidshellInsertSort() {
System.out.println("1、插入排序之->希爾排序");int[] a = { 26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
System.out.println("最初結(jié)果");
printXiEr(a);int j = 0;int temp; //初始化兩個(gè)值//j時(shí)為了第二層循環(huán)，temp為了存儲(chǔ)當(dāng)前值，與其他兩種插入排序不同的時(shí)，本處使用temp，上面兩處使用數(shù)組的第0個(gè)位置存儲(chǔ)
for (int gap = a.length / 2; gap > 0; gap /= 2) {//本次循環(huán)的是增量的值 5 2 1
System.out.println("本次循環(huán)增量為" +gap);for (int i = gap; i < a.length; i++) {//記錄每次的變化，i=gap//相當(dāng)于第一遍先拿a[5]也就是13 來進(jìn)行
temp = a[i]; //temp存儲(chǔ)當(dāng)前的值，與其他兩種插入排序不同的時(shí)，本處使用temp，上面兩處使用數(shù)組的第0個(gè)位置存儲(chǔ)
for (j = i - gap; j >= 0; j -= gap) { //本處循環(huán)是最重要的循環(huán)，也就是移動(dòng)位置的循環(huán)//j=i-gap，第一遍j就等于0//也就是a【0】=26
if (temp < a[j]) { //temp = a[5] = 13//，temp肯定是小于13的，所以執(zhí)行下邊語句
a[j + gap] = a[j]; //將a[j] = 26 放到 j+gap的位置，也就是 0+5//a[5]的位置
} else { //否則跳過本層循環(huán)，記錄執(zhí)行 i=gap的循環(huán)
break;
}
}
a[j+ gap] = temp; //最后把temp的值還原
}
printXiEr(a);
}//輸出結(jié)果
System.out.println("最終結(jié)果：");
printXiEr(a);
}/***
* ======================================
* 1、插入排序之->希爾排序 方法二
*
* 方法二修改方法一的存儲(chǔ)元素的方案，和插入排序前兩個(gè)一樣，采用a[0]來存儲(chǔ)。
* ======================================*/@Testpublic voidshellInsertSort2() {
System.out.println("1、插入排序之->希爾排序2");int[] a = { 0, 26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
System.out.println("最初結(jié)果");
print(a);
System.out.println();int j = 0;//int temp;//初始化兩個(gè)值//j時(shí)為了第二層循環(huán)，temp為了存儲(chǔ)當(dāng)前值，與其他兩種插入排序不同的時(shí)，本處使用temp，上面兩處使用數(shù)組的第0個(gè)位置存儲(chǔ)
for (int gap = a.length / 2; gap > 0; gap /= 2) {//本次循環(huán)的是增量的值 5 2 1
System.out.println("本次循環(huán)增量為" +gap);for (int i = gap; i < a.length; i++) {//記錄每次的變化，i=gap//相當(dāng)于第一遍先拿a[5]也就是13 來進(jìn)行
a[0] = a[i]; //a[0]存儲(chǔ)當(dāng)前的值
for (j = i - gap; j > 0; j -= gap) { //本處循環(huán)是最重要的循環(huán)，也就是移動(dòng)位置的循環(huán)//j=i-gap，第一遍j就等于0//也就是a【0】=26 注意此處改為>0
if (a[0] < a[j]) { //temp = a[5] = 13//，temp肯定是小于13的，所以執(zhí)行下邊語句
a[j + gap] = a[j]; //將a[j] = 26 放到 j+gap的位置，也就是 0+5//a[5]的位置
} else { //否則跳過本層循環(huán)，記錄執(zhí)行 i=gap的循環(huán)
break;
}
}
a[j+ gap] = a[0]; //最后把a(bǔ)[0]的值還原
}
printXiEr(a);
}//輸出結(jié)果
System.out.println("最終結(jié)果：");
print(a);
}/***
* ======================================
* 2、交換排序->冒泡排序
* 冒泡排序最為一種經(jīng)典的排序算法，是我們應(yīng)該隨后都能寫出來的。
* 特點(diǎn)： 1、穩(wěn)定排序
* 2、可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
* 3、移動(dòng)記錄次數(shù)較多，算法平均時(shí)間性能比直接插入排序查。
* 4、當(dāng)記錄無序，n較大時(shí)，此算法不宜采用。
*
* ======================================*/@Testpublic voidBulleSort() {
System.out.println("2、交換排序->冒泡排序");
printXiEr(a);for (int i = 0; i < a.length - 1; i++) { //采用第一層循環(huán)來控制循環(huán)的次數(shù)，一共循環(huán)a.length-1次//這樣會(huì)循環(huán)到倒數(shù)第二個(gè)元素
for (int j = i + 1; j < a.length; j++) {//第二層循環(huán)來交換位置，j在i的基礎(chǔ)上+1是因?yàn)楫?dāng)前的值要和他身后的元素比較大小，直至最后一個(gè)。(//因?yàn)榈诙窝h(huán)直至最后一個(gè)所以第一層循環(huán)才會(huì)a.length-1)
if (a[i] >a[j]) {int temp =a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printXiEr(a);
}/***
* ======================================
* 2、交換排序->快速排序
* 特點(diǎn)： 1、屬于不穩(wěn)定排序
* 2、排序過程中需要確定上界和下屆，所以只能用于順序結(jié)構(gòu)，很難用于鏈?zhǔn)?/p>
* 3、在n較大時(shí)，在平均情況下快速排序是所有內(nèi)部排序中速度最快的一種，所以適合初始記錄無序，n較大的情況
* ======================================*/@Testpublic voidQuickSort() {
System.out.println("待排序序列");
print(a);
Qsort(a,1, a.length - 1);
System.out.println();
print(a);
}private void Qsort(int[] a, int low, intheight) {if (low
point= Partition(a, low, height);//查找中間點(diǎn)
Qsort(a, low, point - 1);//遞歸排序左邊
Qsort(a, point + 1, height);//遞歸排序右邊
}
}private int Partition(int[] a, int low, intheight) {
a[0] = a[low];//將中間點(diǎn)保存在a[0]這個(gè)位置中。
int point = a[low];//把中間點(diǎn)保存在point中
while (low < height) {//循環(huán)條件是只要low
while (low < height && a[height] >= point) {//low
height--;
}
a[low]= a[height]; //循環(huán)結(jié)束后，交換位置，把右邊小的，交換到中間點(diǎn)的左邊
while (low < height && a[low] <= point) { //相反同上， 本來是a[low]>=point//改變寫法 改成a<=point就跳過++；
low++;
}
a[height]=a[low];
}
a[low]= a[0];returnlow;
}//3、選擇排序 直接選擇排序、堆排序、 樹形排序
/***
* ======================================
* 3、選擇排序->直接選擇排序
* 特點(diǎn)：
* 1、是一種穩(wěn)定的排序算法。
* 2、可用于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ======================================*/@Testpublic voidselectSort() {
System.out.println("待排序序列");
print(a);for (int i = 1; i < a.length; i++) {int k =i;for (int j = i + 1; j < a.length; j++) {if (a[k] >a[j]) {
k=j;
}
}if (k !=i) {int temp =a[i];
a[i]=a[k];
a[k]=temp;
}
}
System.out.println();
print(a);
}/***
* ======================================
* 3、選擇排序->堆排序
* 特點(diǎn)：
* 1、不穩(wěn)定排序
* 2、只能用于順序存儲(chǔ)結(jié)構(gòu)
* ======================================*/@Testpublic voidHeapSort() {
CreateHeap();//首先需要?jiǎng)?chuàng)建根堆
for (int i = a.length - 1; i > 1; --i) {//這個(gè)循環(huán)是把最大值a[1]放到末尾 ，
int temp = a[1];
a[1] = a[i]; //此時(shí)i代表最后一個(gè)元素
a[i] =temp;
HeapAdjust(a,1, i - 1);//調(diào)整一次后繼續(xù)，把數(shù)組，第一個(gè)位置，和最后一個(gè)位置 此處為何i-1，//是因?yàn)檠h(huán)已經(jīng)把最大值放到最后一個(gè)了，所以下次就方法最后一個(gè)-1的位置
}
print(a);
}private voidCreateHeap() {int n = a.length - 1; //得到數(shù)組的最大值
for (int i = n / 2; i > 0; i--) { //從最后一個(gè)非終端結(jié)點(diǎn)開始，然后一次--
HeapAdjust(a, i, n);
}
}//調(diào)整堆
private void HeapAdjust(int[] a, int s, int m) {//s代表當(dāng)前 m代表最后
int temp = a[s]; //先把a(bǔ)[s]的值賦給temp保存起來
for (int j = 2 * s; j <= m; j *= 2) {if (j < m && a[j] < a[j + 1]) { //判斷是s大還是s+1大，如果s+1大 就++j，把j換成當(dāng)前最大
++j;
}if (temp >= a[j]) { //如果temp中比最大值還大，代表本身就是一個(gè)根堆，break
break;//如果大于，就代表當(dāng)前為大跟對(duì)，退出
}
a[s]= a[j];//否則就把最大給[s]
s = j;//然后把最大下標(biāo)給s，繼續(xù)循環(huán),檢查是否因?yàn)檎{(diào)整根堆而破壞了子樹
}
a[s]=temp;
}/***
* ======================================
* 4、歸并排序
* 特點(diǎn)：
* 1、屬于穩(wěn)定排序
* 2、可用于鏈?zhǔn)酱鎯?chǔ)
* ======================================*/@Testpublic voidMSortM1() {
print(a);
System.out.println();
Msort(a,1, a.length - 1);
print(a);
}private void Msort(int[] nums, int low, inthight) {int mid = (low + hight) / 2; //求得中間點(diǎn)
if (low < hight) { //判斷條件 如果low
Msort(nums, low, mid); //遞歸左
Msort(nums, mid + 1, hight); //遞歸又
Merge(nums, low, mid, hight); //最后合并
}
}private void Merge(int[] nums, int low, int mid, inthight) {int[] temp = new int[hight - low + 1]; //臨時(shí)數(shù)組，存放本次排序的序列
int i = low; //i代表做序列開頭 j代表又序列開頭 k的作用是針對(duì)temp數(shù)組使用的
int j = mid + 1;int k = 0;while (i <= mid && j <= hight) { //while條件必須滿足兩個(gè)&&條件，只要有一個(gè)不滿足就退出//本次循環(huán)的最后結(jié)果就是 左右兩個(gè)序列，其中一個(gè)序列完全賦值給temp，然后結(jié)束
if (nums[i] < nums[j]) { //比較
temp[k++] = nums[i++]; //賦值
} else{
temp[k++] = nums[j++]; //賦值
}
}//以下兩個(gè)while是針對(duì)上面的while，因?yàn)樯厦娴膚hile最后結(jié)束的結(jié)果為//左右兩個(gè)序列，其中一個(gè)序列完全賦值給temp，然后結(jié)束，這樣其中一個(gè)序列還有值沒有賦給temp//如果是左序列 就對(duì)左序列進(jìn)行賦值
while (i <=mid) {
temp[k++] = nums[i++];
}//如果是又序列 就對(duì)又序列進(jìn)行賦值
while (j <=hight) {
temp[k++] = nums[j++];
}//最后把本次排好序的temp，按照合并前的其實(shí)位置開始，重新賦值給nums； 這種處理方法比數(shù)據(jù)結(jié)構(gòu)書上給的demo處理方式要好。
for (int m = 0; m < temp.length; m++) {
nums[low+ m] =temp[m];
}
}/***
* 基數(shù)排序
**/@Testpublic voidradixSortTest(){
radixSort(a,4,3);
print(a);
}private static void radixSort(int[] array, int radix, intdistance) {//radix，代表基數(shù)//distance代表排序元素的位數(shù) 也就是進(jìn)行幾次 分配 收集，，因?yàn)榇判蛐蛄兄凶畲笾禐?00 三位數(shù) 所以distance為3
int length =array.length;int[] temp = new int[length];//用于暫存元素
int[] count = new int[radix];//用于統(tǒng)計(jì)基數(shù)內(nèi)元素個(gè)數(shù)
int divide = 1;for (int i = 0; i < distance; i++) {
System.arraycopy(array,0, temp, 0, length);
Arrays.fill(count,0);for (int j = 0; j < length; j++) {int tempKey = (temp[j] / divide) %radix;
count[tempKey]++; //基數(shù)選中計(jì)數(shù)
}for (int j = 1; j < radix; j++) {
count[j]= count[j] + count[j - 1];//累計(jì)計(jì)數(shù)
}for (int j = length - 1; j >= 0; j--) {int tempKey = (temp[j] / divide) %radix;
count[tempKey]--;//從后往前賦值
array[count[tempKey]] =temp[j];
}
divide= divide *radix;
}
}/*** 輔助方法，輸出當(dāng)前數(shù)組的值。
*
*@paramtemp
* 接受傳過來的數(shù)組*/
void print(int[] temp) {
System.out.println("排序結(jié)果為：");for (int i = 1; i < temp.length; i++) {
System.out.print(temp[i]+ " ");
}
}/*** 第一種希爾排序的專用抽出方法
*
*@paramtemp*/
void printXiEr(int[] temp) {for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i]+ " ");
}
System.out.println();
}/*** 小測(cè)試，測(cè)試return，break，continue的區(qū)別*/@Testpublic voidaaa() {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++) {if (i == 2) {break;
}
System.out.println(i+ " " +j);
}
}
}
}
總結(jié)
以上是生活随笔為你收集整理的java排序算法代码_Java实现八种排序算法（代码详细解释）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java读取json配置文件_解决：ja
- 下一篇： mysql 主键 uniqo_优衣库某处