# 冒泡排序
# 每次循环,相邻两数字进行比较,满足条件则进行交换
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr=new int[] {5,7,2,9,4,1,0,5,7};
System.out.println(Arrays.toString(arr));
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
//控制共比较多少轮
for(int i=0;i<arr.length-1;i++) {
//控制比较的次数
for(int j=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
# 选择排序
# 每次循环在 n(n=1，2，…n-1)个数字中选取最小的数字的下标, 之后进行交换
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[] {3,4,5,7,1,2,0,3,6,8};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
//选择排序
public static void selectSort(int[] arr) {
//遍历所有的数
for(int i=0;i<arr.length;i++) {
int minIndex=i;
//把当前遍历的数和后面所有的数依次进行比较，并记录下最小的数的下标
for(int j=i+1;j<arr.length;j++) {
//如果后面比较的数比记录的最小的数小。
if(arr[minIndex]>arr[j]) {
//记录下最小的那个数的下标
minIndex=j;
}
}
//如果最小的数和当前遍历数的下标不一致,说明下标为minIndex的数比当前遍历的数更小。
if(i!=minIndex) {
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
}
}
}
# 快速排序
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{2,6,4,1,0,3,8,9,7};
quickSort(arr,0,arr.length-1);
System.out.println( Arrays.toString(arr) );
}
public static void quickSort(int[] arr,int start,int end) {
if(start<end) {
//把数组中的第0个数字做为标准数
int standard=arr[start];
//记录需要排序的下标
int low=start;
int high=end;
//循环找比标准数大的数和比标准数小的数
while(low<high) {
//右边的数字比标准数大
while(low<high&&standard<=arr[high]) {
high--;
}
//使用右边的数字替换左边的数
arr[low]=arr[high];
//如果左边的数字比标准数小
while(low<high&&arr[low]<=standard) {
low++;
}
arr[high]=arr[low];
}
//把标准数赋给低所在的位置的元素
arr[low]=standard;
//处理所有的小的数字
quickSort(arr, start, low-1);
//处理所有的大的数字
quickSort(arr, low+1, end);
}
}
}
# 堆排序
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[] {9,6,8,7,0,1,10,4,2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
//开始位置是最后一个非叶子节点，即最后一个节点的父节点
int start = (arr.length-1)/2;
//调整为大顶堆
for(int i=start;i>=0;i--) {
maxHeap(arr, arr.length, i);
}
//先把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆
for(int i=arr.length-1;i>0;i--) {
int temp = arr[0];
arr[0]=arr[i];
arr[i]=temp;
maxHeap(arr, i, 0);
}
}
public static void maxHeap(int[] arr,int size,int index) {
//左子节点
int leftNode = 2*index+1;
//右子节点
int rightNode = 2*index+2;
int max = index;
//和两个子节点分别对比，找出最大的节点
if(leftNode<size&&arr[leftNode]>arr[max]) {
max=leftNode;
}
if(rightNode<size&&arr[rightNode]>arr[max]) {
max=rightNode;
}
//交换位置
if(max!=index) {
int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
//交换位置以后，可能会破坏之前排好的堆，所以，之前的排好的堆需要重新调整
maxHeap(arr, size, max);
}
}
}
# 插入排序
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[] {5,3,2,8,5,9,1,0};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
//插入排序
public static void insertSort(int[] arr) {
//遍历所有的数字
for(int i=1;i<arr.length;i++) {
//如果当前数字比前一个数字小
if(arr[i]<arr[i-1]) {
//把当前遍历数字存起来
int temp=arr[i];
int j;
//遍历当前数字前面所有的数字
for(j=i-1;j>=0&&temp<arr[j];j--) {
//把前一个数字赋给后一个数字
arr[j+1]=arr[j];
}
//把临时变量（外层for循环的当前元素）赋给不满足条件的后一个元素
arr[j+1]=temp;
}
}
}
}
# 归并排序
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[] {1,3,5,2,4,6,8,10};
System.out.println(Arrays.toString(arr));
mergeSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
//归并排序
public static void mergeSort(int[] arr,int low,int high) {
int middle=(high+low)/2;
if(low<high) {
//处理左边
mergeSort(arr, low, middle);
//处理右边
mergeSort(arr, middle+1, high);
//归并
merge(arr,low,middle,high);
}
}
public static void merge(int[] arr,int low,int middle, int high) {
//用于存储归并后的临时数组
int[] temp = new int[high-low+1];
//记录第一个数组中需要遍历的下标
int i=low;
//记录第二个数组中需要遍历的下标
int j=middle+1;
//用于记录在临时数组中存放的下标
int index=0;
//遍历两个数组取出小的数字，放入临时数组中
while(i<=middle&&j<=high) {
//第一个数组的数据更小
if(arr[i]<=arr[j]) {
//把小的数据放入临时数组中
temp[index]=arr[i];
//让下标向后移一位；
i++;
}else {
temp[index]=arr[j];
j++;
}
index++;
}
//处理多余的数据
while(j<=high) {
temp[index]=arr[j];
j++;
index++;
}
while(i<=middle) {
temp[index]=arr[i];
i++;
index++;
}
//把临时数组中的数据重新存入原数组
for(int k=0;k<temp.length;k++) {
arr[k+low]=temp[k];
}
}
}
