- 冒泡排序
package BubbleSort;
import java.util.Arrays;
public class bubbleSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort(array);
System.out.println(Arrays.toString(array));
}
private 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]) {
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
}
}
}
- 选择排序
package SelectionSort;
import java.util.Arrays;
public class selectionSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
Sort2(array);
System.out.println(Arrays.toString(array));
}
private static void Sort1(int[] array) {
int minIdx = 0;
int tmp;
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIdx]) {
minIdx = j;
}
}
tmp = array[i];
array[i] = array[minIdx];
array[minIdx] = tmp;
}
}
public static void Sort2(int[] array){
int low = 0;
int high = array.length - 1;
// low = high时结束循环，无序区间只剩下一个元素，整个数组已经有序
while(low < high){
// 定义maxIdx，minIdx为无序区间的起始位置索引
int maxIdx = low;
int minIdx = low;
// 无序区间，寻找最大值和最小值
for (int i = low + 1; i <= high; i++) {
if(array[i] < array[minIdx]){
minIdx = i;
}
if(array[i] > array[maxIdx]){
maxIdx = i;
}
}
//将最小值与无序区间起始位置交换
int tmp1 = array[low];
array[low] = array[minIdx];
array[minIdx] = tmp1;
// 如果最大值对应的索引刚好是无序区间的起始位置，经过上面的调整，最大值被调整到了arr[minIdx]位置
if (maxIdx == low){
maxIdx = minIdx;
}
//将最大值与无序区间结束位置交换
int tmp2 = array[high];
array[high] = array[maxIdx];
array[maxIdx] = tmp2;
high--;
low++;
}
}
}
- 插入排序
package InsertionSort;
import java.util.Arrays;
public class insertionSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort2(array);
System.out.println(Arrays.toString(array));
}
private static void sort1(int[] array) {
int tmp;
int tmpIdx;
for (int i = 1; i < array.length; i++) {
tmpIdx = i;
for (int j = i - 1; j >= 0; j--) {
if (array[j] > array[tmpIdx]) {
tmp = array[tmpIdx];
array[tmpIdx] = array[j];
array[j] = tmp;
tmpIdx--;
}
}
}
}
private static void sort2(int[] array) {
for (int i = 1; i < array.length; i++) {
int right = i;
int left = 0;
int tmp = array[i];
while (left < right) {
int mid = left + (right - left) / 2;
if (tmp < array[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
for (int j = i; j > left; j--) {
array[j] = array[j - 1];
}
// left就是tmp插入的位置
array[left] = tmp;
}
}
}
- 希尔排序
package ShellSort;
import java.util.Arrays;
public class shellSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
for (int gap = array.length / 2; gap > 0; gap /= 2) {
int preIdx;
int cur;
for (int i = gap; i < array.length; i++) {
preIdx = i - gap;
cur = array[i];
while (preIdx >= 0 && array[preIdx] > cur) {
//依次往后移动
array[preIdx + gap] = array[preIdx];
preIdx -= gap;
}
array[preIdx + gap] = cur;
}
}
}
}
- 归并排序
package MergeSort;
import java.util.Arrays;
public class mergeSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(array, left, mid);
sort(array, mid + 1, right);
merge(array, left, right);
}
}
private static void merge(int[] array, int left, int right) {
//暂存排序结果
int[] tmp = new int[array.length];
int mid = left + (right - left) / 2;
//指向第一组首元素
int p1 = left;
//指向第二组首元素
int p2 = mid + 1;
//tmp索引
int idx = left;
while(p1 <= mid && p2 <= right) {
if (array[p1] <= array[p2]) {
tmp[idx++] = array[p1++];
} else {
tmp[idx++] = array[p2++];
}
}
//第一组未排完
while(p1 <= mid) {
tmp[idx++] = array[p1++];
}
//第二组未排完
while(p2 <= right) {
tmp[idx++] = array[p2++];
}
//将排序后的结果赋予array
for(int i = left; i <= right; ++i) {
array[i] = tmp[i];
}
}
}
- 快速排序
选取最左边的值为基准
package MergeSort;
import java.util.Arrays;
public class mergeSort {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(array, left, mid);
sort(array, mid + 1, right);
merge(array, left, right);
}
}
private static void merge(int[] array, int left, int right) {
//暂存排序结果
int[] tmp = new int[array.length];
int mid = left + (right - left) / 2;
//指向第一组首元素
int p1 = left;
//指向第二组首元素
int p2 = mid + 1;
//tmp索引
int idx = left;
while(p1 <= mid && p2 <= right) {
if (array[p1] <= array[p2]) {
tmp[idx++] = array[p1++];
} else {
tmp[idx++] = array[p2++];
}
}
//第一组未排完
while(p1 <= mid) {
tmp[idx++] = array[p1++];
}
//第二组未排完
while(p2 <= right) {
tmp[idx++] = array[p2++];
}
//将排序后的结果赋予array
for(int i = left; i <= right; ++i) {
array[i] = tmp[i];
}
}
}
选取中间值为基准
package QuickSort;
import java.util.Arrays;
public class quickSort_middle {
public static void main(String[] args) {
int[] array = new int[]{2,10,8,22,34,5,12,28,21,11};
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array,int left,int right){
int l = left;
int r = right;
//基准值
int index = array[l + (r - l) / 2];
int temp = 0;
while(l < r) {
while (array[l] < index) {
l++;
}
while (array[r] > index) {
r--;
}
if (l >= r) {
break;
}
temp = array[l];
array[l] = array[r];
array[r] = temp;
//如果array[l] = index，说明之前r所指位置的元素为index，需要向前移动
if (array[l] == index) {
r--;
}
//如果array[r] = index，说明之前l所指位置的元素为index，需要向后移动
if (array[r] == index) {
l++;
}
}
//while结束时l = r，且所在位置是index元素的正确位置
//分别对左右序列继续排序
if(left < r) {
sort(array, left, r - 1);
}
if(right > l) {
sort(array, l + 1, right);
}
}
}
