Java算法 - 排序算法
插入排序
思路簡介
假定待排序數(shù)組長度為N童本，假設(shè)前n-1個數(shù)已經(jīng)排好序借嗽，通過比較第n個數(shù)與前n-1個數(shù)的大小曲管，確定第n個數(shù)的位置簇爆，通過移位的方式將第n個數(shù)插入到前n-1個有序數(shù)組中。邊界條件就是n=2视译，只有一個數(shù)的時候默認(rèn)是排好序的嬉荆。
程序示例
package sort;
import java.util.Arrays;
public class InsertSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34,
15
};
public static void Sort(int[] array)
{
for (int i = 1; i < array.length; i++)
{
int tmp = array[i];
int j = i - 1;
for (; j >= 0 && array[j] > tmp; j--)
{
array[j + 1] = array[j];
}
array[j + 1] = tmp;
}
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
希爾排序
思路簡介
希爾排序是對插入排序的一種改良算法。希爾排序是將待排序數(shù)組的元素分組進行插入排序酷含。我們使用gap來表示分組元素之間的間隔员寇。標(biāo)準(zhǔn)的希爾排序算法，gap的取值是從1/2 length到1第美，其中迭代公式為gap/=2。
在插入排序的兩重循環(huán)的基礎(chǔ)上陆爽，我們還要添加一個循環(huán)用于迭代gap什往。
程序示例
package sort;
import java.util.Arrays;
public class ShellSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15
};
public static void Sort(int[] array)
{
for (int gap = array.length / 2; gap >= 1; gap /= 2)
{
for (int i = gap; i < array.length; i++)
{
int tmp = array[i];
int j = i - gap;
for (; j >= 0 && array[j] > tmp; j-=gap)
{
array[j + gap] = array[j];
}
array[j + gap] = tmp;
}
}
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
簡單選擇排序
思路簡介
簡單選擇排序就是從待排序數(shù)組中選擇一個最小的放在與數(shù)組的第一位進行交換，然后再從除第一位之外剩余的數(shù)中選擇一個最小的與數(shù)組的第二組進行交換慌闭，直到數(shù)組的最后兩位進行比較别威，是一個效率非常低的排序算法
程序示例
package sort;
import java.util.Arrays;
public class SelectSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15
};
public static void Sort(int[] array)
{
for (int i = 0; i < array.length - 1; i++)
{
int min = array[i];
int k = i;
for (int j = i + 1; j < array.length; j++)
{
if (array[j] < min)
{
min = array[j];
k = j;
}
}
array[k] = array[i];
array[i] = min;
}
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
堆排序
思路簡介
堆排序是一種基于完全二叉樹的選擇排序。在介紹這個算法之前驴剔，首先要弄清楚大頂堆和頂堆的概念省古。
大頂堆：樹中每個節(jié)點的值都比其子節(jié)點的值大。（用作從小到大）
小頂堆：樹中每個節(jié)點的值都比其子節(jié)點的值小丧失。（用作從大到胁蚣恕）
我們按照將樹上的節(jié)點按照從上到小（從根），從左到右進行編號（從0開始）琳拭，這些編號對應(yīng)了待排序數(shù)組的下標(biāo)训堆，例如一個待排序數(shù)組為[9 8 7 6 5 4 3 2 1]，將它表示為如下圖所示的樹
幾個特殊的位置對應(yīng)的數(shù)學(xué)表達(dá)式：
最后一個非葉子節(jié)點：length/2 - 1
一個節(jié)點i的左子節(jié)點：2 * i + 1
一個節(jié)點I的右子節(jié)點：2 * i + 2
有了上述基本概念白嘁，我們就可以開始理解堆排序了坑鱼。堆排序分為兩個步驟：
- 調(diào)整堆使堆滿足大頂堆（小頂堆）的定義。（將最大（最行趺濉）的元素移到了根節(jié)點）
- 然后交換大頂堆（小頂堆）的根節(jié)點與堆的最后一個節(jié)點鲁沥，堆的長度減一后，重新從根節(jié)點開始調(diào)整堆耕魄。重復(fù)步驟2直到堆的長度減為1画恰。（將最大（最小）的元素移動了數(shù)組的末尾）
程序示例
package sort;
import java.util.Arrays;
public class HeapSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15
};
public static void Sort(int[] array)
{
//從最后一個非葉子節(jié)點調(diào)整堆屎开，使其滿足大頂端的定義
for (int i = array.length / 2 - 1; i >= 0; i--)
{
AdjustHeap(array, i, array.length);
}
//第二階段阐枣，交換元素并調(diào)整堆
for (int i = array.length - 1; i > 0; i--)
{
swap(array, 0, i);
AdjustHeap(array, 0, i);
}
}
public static void AdjustHeap(int[] array, int i, int length)
{
int tmp = array[i];
for (int j = 2 * i + 1; j < length; j = 2 * j + 1)
{
if (array[j] < array[j + 1] && j + 1 < length)
{
j++;
}
if (array[j] > tmp)
{
array[i] = array[j];
i = j;
}
else {
break;
}
}
array[i] = tmp;
}
public static void swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
冒泡排序
思路簡介
比較待排序的數(shù)組相鄰兩個元素，如何他們的順序與排序要求不同奄抽，則交換兩個元素蔼两。每一次冒泡可以將一個最大（最小）的元素移動到數(shù)組最后逞度《罨總得次數(shù)取決的待排序數(shù)組的長度，次數(shù)=length - 1档泽。
程序示例
package sort;
import java.util.Arrays;
public class BubbleSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15
};
public static void Sort(int[] array)
{
for (int i = 0; i < array.length - 1; i++)
{
for (int j = 0; j < array.length - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
swap(array, j, j + 1);
}
}
}
}
public static void swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
快速排序
思路簡介
快速排序使用了分治(device and conquer)的思想俊戳，將待排序的數(shù)組以某個數(shù)k為基準(zhǔn)，分成左右兩部分馆匿。以增序為例抑胎，k左邊的數(shù)均比k小，k右邊的數(shù)均比k大渐北。然后遞歸地對這兩部分使用快速排序阿逃。遞歸地結(jié)束條件是每個部分的數(shù)據(jù)長度為1。
難點在于如何在O(n)的時間里實現(xiàn)兩部分的拆分赃蛛。一般k取數(shù)組的第一個元素恃锉。
使用指針i和j分別指向數(shù)組的第一個元素和最后一個元素。
如果a[i] <= a[j] j--呕臂，直到找到了一個j破托，使a[i] > a[j]，那么交換a[j]和a[i]歧蒋。
如何a[i] <= a[j] i++土砂，直到找到了一個i州既，使a[i] > a[j]，那么交換a[j]和a[i]瘟芝。
指針的終止條件是i < j 易桃。
程序示例
package sort;
import java.util.Arrays;
public class QuickSort
{
private static int[] testcase = {
49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64,
5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15
};
public static void Sort(int[] array)
{
quickSort(array, 0, array.length - 1);
}
public static void quickSort(int[] array, int start, int end)
{
if (start >= end)
{
return;
}
int i = start;
int j = end;
while (i != j)
{
while (array[i] <= array[j] && i < j)
j--;
swap(array, i, j);
while (array[i] <= array[j] && i < j)
i++;
swap(array, i, j);
}
quickSort(array, start, i - 1);
quickSort(array, i + 1, end);
}
public static void swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void main(String[] args)
{
System.out.println("origin array:" + Arrays.toString(testcase));
Sort(testcase);
System.out.println("after sort:" + Arrays.toString(testcase));
}
}
