幾種常見排序算法思想及其實作
1.冒泡排序
排序思想：先找出數組中最大的元素，放在最右邊，然後找出第二大的，放在右邊第二個位置…
注：與選擇排序不同的是，冒泡排序在找最大元素時，邊比較邊交換，而選擇排序是找到最小的再交換，這也是冒泡排序穩定，而選擇排序不穩定的原因
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,4,7,9,8,0,6};
// int[] selectionSort = sort(arr);
int[] selectionSort = sort2(arr);
for (int item: selectionSort) {
System.out.println(item);
}
}
private static int[] sort(int[] arr) {
int len = arr.length;
if(len <= 1){
return arr;
}
for (int i = 0; i < len; i++) {
for (int j = 0; j < len - i -1; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
/**
* 冒泡排序優化
* @param arr
* @return
*/
private static int[] sort2(int[] arr) {
int len = arr.length;
if(len <= 1){
return arr;
}
for (int i = 0; i < len; i++) {
boolean flag = true;
for (int j = 0; j < len - i -1; j++) {
if(arr[j] > arr[j+1]) {
flag = false;
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(flag){
break;
}
}
return arr;
}
}
2.選擇排序
排序思想：先找到數組中最小的元素，與數組第一個元素交換位置，然後找出剩餘元素中最小的元素，與數組第二個位置交換…
public class SelectionSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,4,7,9,8,0,6};
int[] selectionSort = sort(arr);
for (int item: selectionSort) {
System.out.println(item);
}
}
private static int[] sort(int[] arr) {
int len = arr.length;
//周遊整個數組
for (int i = 0; i < len; i++) {
int min = i;
//周遊無序部分
for (int j = i + 1; j < len; j++) {
if(arr[min] > arr[j]) {
min = j;
}
}
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
}
3.插入排序
排序思想：将右邊無序元素依次插入到左邊有序元素中，剛開始将第一個元素作為左邊有序數組
public class InsertionSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,4,7,9,8,0,6};
int[] selectionSort = sort(arr);
for (int item: selectionSort) {
System.out.println(item);
}
}
private static int[] sort(int[] arr) {
int len = arr.length;
if(len <= 1){
return arr;
}
for (int i = 1; i < len; i++) {
//要插入的資料
int temp = arr[i];
//要插入的位置的前一個位置
int j = i - 1;
while (j >= 0 && temp < arr[j]){
j--;
}
//移動數組,k是需要移動的元素的索引
for (int k = i - 1; k > j; k--) {
arr[k+1] = arr[k];
}
arr[j+1] =temp;
}
return arr;
}
}
4.歸并排序
排序思想（分治）：首先，将一個大的數組遞歸分割，直到數組的大小都為1，我們認為大小為 1的數組是有序的。然後，我們将大小為1的數組合并成大小為2的數組，将大小為2的數組合并成大小為4的數組…
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,4,7,9,8,0,6};
int[] selectionSort = sort(arr, 0, arr.length-1);
// int[] selectionSort = sort2(arr);
for (int item: selectionSort) {
System.out.println(item);
}
}
/**
* 遞歸式歸并排序(分而治之)
* @param arr
* @return
*/
private static int[] sort(int[] arr, int left, int right) {
//遞歸結束的條件：遞歸到隻有一個元素，即left == right
if(left < right){
//分
int mid = left + (right - left) / 2;
//治
sort(arr, left, mid);
sort(arr, mid + 1, right);
//合
merge(arr, left, mid, right);
}
return arr;
}
/**
* 合并有序數組
* @param arr
* @param left
* @param mid
* @param right
*/
private static void merge(int[] arr, int left, int mid, int right) {
int i = left;
int j= mid + 1;
int[] temp =new int[right - left + 1];
for (int k = 0; k < temp.length ; k++) {
//如果左邊（右邊）數組元素取完，則直接複制右邊（左邊）數組
if(i > mid) {
temp[k] = arr[j++];
}else if(j > right) {
temp[k] = arr[i++];
}else if(arr[i] <= arr[j]){
temp[k] = arr[i++];
}else {
temp[k] = arr[j++];
}
}
//将臨時數組的值複制到原數組 arr 中
for (int k = 0; k < temp.length ; k++) {
arr[left++] = temp[k];
}
}
}
5.快速排序
排序思想（分治）：首先，從數組中選擇一個元素作為中軸元素（一般選第一個元素，或者也可随機擷取），将小于中軸元素的元素放在中軸元素左邊，大于中軸元素的放在中軸元素右邊，此時中軸元素有序。然後，将中軸元素左邊部分和右邊部分也重複同樣的操作（通過遞歸），直到數組的大小為1，此時每個元素都有序。
注：快速排序應該注意，如果選擇左邊第一個數為中軸元素，則應該先移動右邊下标 j ，如果選擇右邊第一個元素為中軸元素，應該先移動左邊下标 i
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,4,7,9,8,0,6};
quickSort(arr, 0, arr.length - 1);
for (int item:arr) {
System.out.println(item);
}
}
/**
* 遞歸快排
* @param arr
* @param left
* @param right
* @return
*/
private static void quickSort(int[] arr, int left, int right){
if (left < right){
int mid = partition(arr,left,right);
quickSort(arr,left,mid-1);
quickSort(arr,mid+1,right);
}
}
public static int partition(int[] arr, int left, int right){
int pivot = arr[left];
int i = left;
int j = right;
while(i < j){
while(i < j && arr[j] >= pivot){
j--;
}
while(i < j && arr[i] <= pivot){
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[i];
arr[i] = pivot;
return i;
}
}
6.堆排序
排序思想：将無序數組建構成二叉堆，将堆頂元素與最後一個元素交換，将剩餘元素再次構成一個二叉堆，再把堆頂元素與第二個元素交換…
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[]{5,3,4,7,9,8,0,6};
heapSort(arr);
for (int item: arr) {
System.out.println(item);
}
}
/**
* 堆排序
* @param arr
*/
private static void heapSort(int[] arr){
int n = arr.length;
//建構大頂堆
for (int i = (n-2)/2; i >= 0; i--) {
downAdjust(arr, i, n-1);
}
//進行堆排序
for (int i = n - 1; i >= 1; i--) {
//将堆頂元素與第一個元素交換
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//恢複二叉堆
downAdjust(arr,0,i-1);
}
}
/**
* 下沉操作，建構二叉堆
* @param arr
* @param parent
* @param n
*/
private static void downAdjust(int[] arr, int parent, int n){
//臨時儲存要下沉的元素
int temp = arr[parent];
//定位左孩子節點的位置
int child = 2 * parent + 1;
//開始下沉
while (child <= n){
// 如果右孩子節點比左孩子大，則定位到右孩子
if(child + 1 <= n && arr[child] < arr[child + 1]){
child++;
}
// 如果孩子節點小于或等于父節點，則下沉結束
if (arr[child] <= temp ){
break;
}
// 父節點進行下沉
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
arr[parent] = temp;
}
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)