八大排序
- 冒泡排序（稳定）
- 选择排序（不稳）
- 插入排序（稳定）
- 希尔排序（不稳）
- 快速排序（不稳）
- 归并排序（稳定）
- 基数排序（稳定）
- 堆排序（不稳）
冒泡排序（稳定）
public class BubbleSort {
public static void main(String[] args) {
bubbleSort(ArrayTest.ARRAY);
System.out.println(Arrays.toString(ArrayTest.ARRAY));
}
private static void bubbleSort(int[] array) {
int temp = 0;
for (int i = 0; i < array.length - 1; i++) {
boolean flag = true;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
flag = false;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
if (flag){
break;
}
}
}
}
选择排序（不稳）
public class SelectSort {
public static void main(String[] args) {
selectSort(ArrayTest.ARRAY);
System.out.println(Arrays.toString(ArrayTest.ARRAY));
}
private static void selectSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int min = array[i];
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
minIndex = j;
}
}
if (minIndex != i){
array[minIndex] = array[i];
array[i] = min;
}
}
}
}
插入排序（稳定）
public class InsertSort {
public void insertSort(int[] arr) {
if (arr == null || arr.length <= 0) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
private void swap(int[] arr, int i, int i1) {
int temp = arr[i];
arr[i] = arr[i1];
arr[i1] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 9, 4, 3, 8, 2, 1, 6};
InsertSort insertSort = new InsertSort();
insertSort.insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
希尔排序（不稳）
public class ShellSort {
public static void main(String[] args) {
shellSort(ArrayTest.ARRAY);
System.out.println(Arrays.toString(ArrayTest.ARRAY));
}
private static void shellSort(int[] array) {
for (int gap = array.length >> 1; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int insertVal = array[i];
int insertIndex = i;
while (insertIndex - gap >= 0 && insertVal < array[insertIndex - gap]){
array[insertIndex] = array[insertIndex - gap];
insertIndex -= gap;
}
array[insertIndex] = insertVal;
}
}
}
}
快速排序（不稳）
public class QuickSort {
public static void main(String[] args) {
quickSort(ArrayTest.ARRAY,0,ArrayTest.ARRAY.length - 1);
System.out.println(Arrays.toString(ArrayTest.ARRAY));
}
private static void quickSort(int[] array, int left, int right) {
if (left >= right) return;
int mid = partition(array, left, right);
quickSort(array, left, mid - 1);
quickSort(array, mid + 1, right);
}
private static int partition(int[] array, int left, int right) {
int pivot = array[right];
int l = left;
int r = right - 1;
while (l <= r) {
while (l <= r && pivot >= array[l]) l++;
while (l <= r && pivot < array[r]) r--;
if (l < r){
int temp = array[l];
array[l] = array[r];
array[r] = temp;
}
}
int temp = array[right];
array[right] = array[l];
array[l] = temp;
return l;
}
}
归并排序（稳定）
public class MergeSort {
public void process(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
process(arr, left, mid);
process(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int tempIndex = 0;
int l = left;
int r = mid + 1;
while (l <= mid && r <= right) {
temp[tempIndex++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
}
while (l <= mid) {
temp[tempIndex++] = arr[l++];
}
while (r <= right) {
temp[tempIndex++] = arr[r++];
}
for (int i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 1, 9, 7, 34, 6, 8};
MergeSort mergeSort = new MergeSort();
mergeSort.process(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
基数排序（稳定）
public class MergeSort {
public void process(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
process(arr, left, mid);
process(arr, mid + 1, right);
merge(arr, left, mid, right);
}
private void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int tempIndex = 0;
int l = left;
int r = mid + 1;
while (l <= mid && r <= right) {
temp[tempIndex++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
}
while (l <= mid) {
temp[tempIndex++] = arr[l++];
}
while (r <= right) {
temp[tempIndex++] = arr[r++];
}
for (int i = 0; i < temp.length; i++) {
arr[left + i] = temp[i];
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 1, 9, 7, 34, 6, 8};
MergeSort mergeSort = new MergeSort();
mergeSort.process(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
堆排序（不稳）
public class HeapSort {
public void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
adjustHeap(arr, i);
}
// for (int i = arr.length - 1; i >= 0 ; i--) {
// heapfyi(arr,i,arr.length);
// }
int heapSize = arr.length;
swap(arr, 0, --heapSize);
while (heapSize > 0) {
heapfyi(arr, 0, heapSize);
swap(arr, 0, --heapSize);
}
}
private void heapfyi(int[] arr, int index, int heapSize) {
//左孩子
int left = index * 2 + 1;
while (left < heapSize) {
//顺序必须是arr[left+ 1] > arr[left] ，因为前者成立的情况下才会进行比较，如果前者不成立，只能返回left。
int largest = left + 1 < heapSize && arr[left+ 1] > arr[left ] ? left + 1 : left;
largest = arr[index] > arr[largest] ? index : largest;
if (largest == index) {
break;
}
swap(arr, index, largest);
index = largest;
left = index * 2 + 1;
}
}
private void adjustHeap(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
private void swap(int[] arr, int index, int i) {
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 7, 6, 1, 3, 0};
HeapSort heapSort = new HeapSort();
heapSort.heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
