- 冒泡排序
冒泡排序本质是类似于小鱼吐泡泡。由小到大。
排序规则是相邻之间的两个元素之间进行交换。
大圈套小圈。大全共循环数组的长度次数
for(int i=0;i<arr.length;i++){
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) { 相邻元素比较
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
- 选择排序
/**
* 选择排序
* 简介：先寻找最大值（最小值），然后在剩下的值里面继续寻找最大值（最小值）
*
*/
public static void selectSort(int[] data){
for (int i = 0; i < data.length-1; i++) { //循环次数
int num=i;
for(int j=i+1;j<data.length;j++){ //从i+1开始比较 一直到最后一个值
if(data[j]>data[num]){
num=j;
}
}
//找到最大值然后与前面的值交换
int temp=data[num];
data[num]=data[i];
data[i]=temp;
}
}
- 插入排序
/**
* 插入排序
* 简介：依次将后面的值与前面的值做比较（从前面的最后一个开始）。
*
* 这样当数据本来就是有序的时候，时间复杂度为 O（n）
* 最坏情况复杂度为 O(n^2)
*
*/
public static void insertSort(int[] data){
/**
*比较过程类似冒泡，
*/
for (int i = 1; i < data.length; i++) { //把第一个空出来 用后面的挨个与前面的作比较然后插入
for(int j=i-1;j>=0;j--){ //与前面的最后一个做比较，一旦比前面的小就交换，否则直接推出循环
if(data[j+1]<data[j]){
int temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}else{
break;
}
}
}
}
- 希尔排序
/**
*希尔排序
*简介：升级版的插入排序， 先将数据进行分组，然后将分组的数据进行插入排序
*
*/
public static void shellSort(int[] data){
for(int a=data.length/2;a>0;a/=2){ // 将数据分组
for(int i=a;i<data.length;i++){ //将每次分组的数据进行插入排序
for(int j=i-a;j>=0;j-=a){ //只与本组数据进行比较
if(data[j]>data[j+a]){
int temp=data[j];
data[j]=data[j+a];
data[j+a]=temp;
}else{
break;
}
}
}
}
}
- 快速排序
在数组里面选择一个数为基准，比基准小的数排在左边，比基本大的数排在右边。
然后继续采用上述规则进行排序左边和右边的数组-递归
public class QuickSort {
public static void main(String[] args) {
int [] arr=new int[8];
for(int i=0;i<arr.length;i++){
arr[i]=(int)(Math.random()*8);
}
System.out.println(Arrays.toString(arr));
quickSort(arr,0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int low,int high){
if(low<high){
int index = getIndex(arr, low, high);
quickSort(arr,low,index-1);
quickSort(arr,index+1,high);
}
}
/**
* 返回一次排序完基准数据的位置
* @param arr
* @param low
* @param high
* @return
*/
public static int getIndex(int[] arr ,int low,int high){
int temp=arr[low];
while(low<high){
while(low<high&&arr[high]>=temp){
high--;
}
arr[low]=arr[high];
while(low<high&&arr[low]<=temp){
low++;
}
arr[high]=arr[low];
}
arr[low]=temp;
return low;
}
}
- 堆排序
通过数组先构建大顶堆，然后将数组的第一个也就是最大值与最后一个交换，然后将除最后一个外的数组继续构建大顶堆，直到排好。
public static void main(String[] args) {
int[] arr=new int[8];
for (int i = 0; i < arr.length; i++) {
arr[i]=(int)(Math.random()*8);
}
System.out.println(Arrays.toString(arr));
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr){
//从最后一个非叶子节点开始，将整个数组构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){ //arr.length/2-1是最后一个非叶子节点
adjustSort(arr,i, arr.length);
}
for(int j= arr.length-1;j>0;j--){
swap(arr,0,j); //将第一个数与最后一个数交换，然后再次构建大顶堆 直到排好
adjustSort(arr,0,j);
}
}
public static void swap(int arr[],int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
//根据当前节点到数组最后构建大顶堆
public static void adjustSort(int[] arr,int i,int length){
int temp=arr[i];
for(int k= 2*i+1;k<length;k=k*2+1){ // 2*i+1 是i节点的左子树
if(k+1<length&&arr[k]<arr[k+1]){
k++;
}
if(arr[k]>temp){
arr[i]=arr[k];
i=k;
}else{
break;
}
}
arr[i]=temp;
}
|