冒泡排序
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length - i - 1; j++) {
if(array[j] > array[j + 1]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
堆排序
/**
* 堆排序
*
* 大堆的特点：父节点始终比叶子节点要大或相等
*
* 大堆是完全二叉树，父节点为 i，左节点为 2i，右节点为 2i + 1；
*
* 创建大堆，不断重排大堆，依次将大堆的根节点取出来
*/
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
buildMaxHeap(array);
for(int i = array.length - 1; i >= 1; i--) {
// 将最大的数排到后面
swap(array, 0, i);
maxHeap(array, i, 0);
}
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
// 创建大堆
private static void buildMaxHeap(int[] array) {
// 2i + 2 = n - 1
int i = (array.length - 1) / 2;
for(; i >= 0; i--) {
maxHeap(array, array.length, i);
}
}
private static void maxHeap(int[] array, int length, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int high = i;
if(left < length && array[i] < array[left]) {
high = left;
}
if(right < length && array[high] < array[right]) {
high = right;
}
if(high != i) {
swap(array, i, high);
maxHeap(array, length, high);
}
}
private static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
插入排序
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
for (; j >= 0 && array[j] > temp; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;
}
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
二分法查找插入排序
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
for(int i = 1; i < array.length; i++) {
int left = 0;
int right = i - 1;
int temp = array[i];
while(left <= right) {
int mid = (left + right) / 2;
if(array[mid] < array[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
for(int j = i - 1; j >= left; j--) {
array[j + 1] = array[j];
}
array[left] = temp;
}
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
希尔排序
/**
* 希尔排序
*
* 该算法的原理将 数组进行多次分组后，在分组内进行插入排序
*
* 时间复杂度优于直接插入排序，但不稳定
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
int d = array.length;
while (true) {
d /= 2;
for (int i = 0; i < d; i++) {
// 分组进行插入排序
for (int j = i + d; j < array.length; j += d) {
int temp = array[j];
int k = j - d;
for(; k >= 0 && array[k] > temp; k -= d) {
array[k + d] = array[k];
}
array[k + d] = temp;
}
}
if (d == 1) {
break;
}
}
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
}
快速排序
/**
* 原理 将数组的第一个数作为基数，不断的和左右两端的数进行比较，把比他大的数放在他的右边，比他小的数放在左边，直到找到他的正确位置。
* 依次将其左右两边的数进行快速排序。
*/
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
private static void quickSort(int[] a, int low, int high) {
if (low < high) {
int middle = getMiddle(a, low, high);
quickSort(a, low, middle - 1);
quickSort(a, middle + 1, high);
}
}
/**
* 找到该值在排序后正确的位置
*/
private static int getMiddle(int[] a, int low, int high) {
int temp = a[low];
while (low < high) {
while (low < high && a[high] >= temp) {
high--;
}
a[low] = a[high];
while (low < high && a[low] <= temp) {
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}
private static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
归并排序
/**
* 归并排序
*
* 原理
*
* 将数组不断进行分割成若干个小数组（分割到最后，每个数组剩两个），然后将这些个小数组进行合并
*/
public static void main(String[] args) {
int[] array = new int[] { 12, 3, 19, 0, -21, -45, 23, 67, 43, 90, 22, 11 };
mergeSort(array, 0, array.length - 1);
for(int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/**
* 将数组不断分割成多个小数组
*/
public static void mergeSort(int[] array, int left, int right) {
if(left < right) {
int middle = (left + right) / 2;
mergeSort(array, left, middle);
mergeSort(array, middle + 1, right);
merge(array, left, middle, right);
}
}
/**
* 将数组进行合并
*/
public static void merge(int[] array, int left, int middle, int right) {
int[] tempArray = new int[array.length];
int start = left;
int tempStart = left;
int rightStart = middle + 1;
while(left <= middle && rightStart <= right) {
if(array[left] < array[rightStart]) {
tempArray[tempStart++] = array[left++];
} else {
tempArray[tempStart++] = array[rightStart++];
}
}
// 如果左边还有元素没合并进去，追加到数组的最后
while(left <= middle) {
tempArray[tempStart++] = array[left++];
}
// 如果右边还有元素没合并进去，追加到数组的最后
while(rightStart <= right) {
tempArray[tempStart++] = array[rightStart++];
}
// 将临时数组拷贝到原数组中
while(start <= right) {
array[start] = tempArray[start++];
}
}
