java实现各种排序算法

插入排序

public static void insertSort(int[] arr){
for(int i = 0 ; i < arr.length ; i ++){
int tmp = arr[i];
int j = 0;
for(j = i - 1; (j > -1) && (tmp < arr[j]) ; j --){
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = tmp;
        }

起泡排序

    public static void bubbleSort(int[] arr){
int length = arr.length - 1;
int tmp = 0;
boolean flag = false;
while(length != 0){
            flag = false;
for(int i = 0; i < length ; i ++){
if(arr[i] > arr[i+1]){
                    tmp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = tmp;
                    flag = true;
                }
            }
            System.out.println("第"+(arr.length-length)+"趟："+Arrays.toString(arr));
            length--;

if(flag == false){
//这个过程中不曾出现数据交换的动作，说明数组已经是有序的了
break;
            }
        }
    }

选择排序

（1）：将序列分成有序区和无序区，初始时有序区为空，无序区包括全部元素
（2）：每次从无序区中选择最小的元素将其与无序区第一个元素进行交换
（3）：重复（2）,直到无序区没有元素

    public static void selectSort(int[] arr){
int tmp = 0; 
int index = 0;
for(int i = 0 ; i < arr.length ; i ++){
            index = i;
//查找[i...length]中的最小值
for(int j = i + 1; j < arr.length; j ++){
if(arr[index] > arr[j]){
                    index = j;
                }
            }
//最小元素不是本身
if(index != i){
                tmp = arr[index];
                arr[index] = arr[i];
                arr[i] = tmp;
            }
        }
    }

##归并排序

public static void mergeSort(int[] list){
if(list.length > 1){
//合并左半部分
int[] leftHalf = new int[list.length/2];
            System.arraycopy(list,0,leftHalf,0,list.length/2);
            mergeSort(leftHalf);

//合并右半部分
int rightHalfLength = list.length - list.length / 2;
int[] rightHalf = new int[rightHalfLength];
            System.arraycopy(list,list.length / 2,rightHalf,0,rightHalfLength);
            mergeSort(rightHalf);

int[] temp = merge(leftHalf,rightHalf);
            System.arraycopy(temp,0,list,0,temp.length);
        }
    }
public static int[] merge(int[] list1,int[] list2){
int[] temp = new int[list1.length + list2.length];
int pos1 = 0;//list1游标
int pos2 = 0;//list2游标
int pos3 = 0;//temp游标

while(pos1 < list1.length && pos2 < list2.length){
if(list1[pos1] < list2[pos2]){
                temp[pos3++] = list1[pos1++];
            }else if(list1[pos1] > list2[pos2]){
                temp[pos3++] = list2[pos2++];
            }else{
                temp[pos3++] = list2[pos2++];
                temp[pos3++] = list1[pos1++];
            }
        }
while(pos1 < list1.length){
            temp[pos3++] = list1[pos1++];
        }
while(pos2 < list2.length){
            temp[pos3++] = list2[pos2++];
        }
return temp;
    }

快速排序

public static void quickSort(int[] arr,int low,int high){
if(high > low){
int part = partition(arr,low,high);
//System.out.println("part="+part);
            quickSort(arr,low,part - 1);
            quickSort(arr,part+1,high);
        }
    }
//找寻分界点
public static int partition(int[] arr,int low , int high){
int first = low;
int pivot = arr[low];
        low++;
while(high > low){
//从左边找比pivot大的数
while(low <= high && arr[low] <= pivot ){
                low++;
            }
//从右边找比pivot小或等于的数
while(high >= low && arr[high] > pivot ){
                high--;
            }
//交换
if(high > low){
int temp = arr[high];
                arr[high] = arr[low];
                arr[low] = temp;
            }
        }
//此时high = low - 1;
//且high之前的元素都小于等于pivot,low之后的元素都大于pivot
//System.out.println("low="+low+";high="+high+"："+Arrays.toString(arr));
if(high > first){
int temp = arr[high];
            arr[high] = arr[first];
            arr[first] = temp;
//System.out.println("part="+high+"："+Arrays.toString(arr));
return high;
        }else{
//System.out.println("part="+high+"："+Arrays.toString(arr));
return first;
        }
    }

堆排序

堆是一棵具有以下属性的二叉树
    1、一棵完全二叉树
    2、每个节点大于（小于）或等于它的任意一个孩子
    分类：大顶堆，小顶堆

    public static void heapSort(int arr[]){
//初始化堆
        initHeap(arr);
//System.out.println("初始化堆：" + Arrays.toString(arr));
//end表示堆的结束位置
int end = arr.length - 1;
while(end > 0){
//删除堆顶元素
int temp = arr[0];
            arr[0] = arr[end];
            arr[end] = temp;
            end--;
if(end > 0){
//调整堆
                adjustHeap(arr,end);
            }
        }
    }
public static void initHeap(int[] arr){
//从0计数，则位置i的节点，左孩子在位置2i+1处，右孩子在位置2i+2处，而父节点在(i-1)/2处
for(int i = 1 ; i < arr.length ; i ++){
int current = i;
while(current > 0){
int parent = (current - 1) / 2;
//孩子节点大于父节点，则交换位置
if(arr[current] > arr[parent]){
int temp = arr[current];
                    arr[current] = arr[parent];
                    arr[parent] = temp;
//向上调整，跟新current
                    current = parent;
                }else{
break;
                }
            }
        }
    }
public static void adjustHeap(int[] arr,int end){
//删除堆顶元素后，调整堆顶的位置
//需要知道的是，由于删除堆顶只是调整了堆顶的元素值，
//因此除去堆顶之后，左右都是符合堆的树，
//如此将堆顶元素向下调整的时候，如果检测到堆顶元素符合堆的定义时，
//而由于它的左右子树始终是符合堆的定义，因此调整过程可以结束
int current = 0;
while(current < end){   
int left = current * 2 + 1;
int right = current * 2 + 2;
if(left <= end && right <= end){
//左右节点都存在
if(!(arr[current] >= arr[left] && arr[current] >= arr[right])){
//需要进行调整堆顶
int index = left;
if(arr[left] < arr[right]){
//左节点小于右节点
                        index = right;
                    }
int temp = arr[current];
                    arr[current] = arr[index];
                    arr[index] = temp;
                    current = index;
                }else{
//此时已经是堆了，无需继续向下调整
break;
                }
            }else if(left <= end && right > end){
//左节点存在但右节点不存在 
if(arr[current] < arr[left]){
int temp = arr[current];
                    arr[current] = arr[left];
                    arr[left] = temp;
                    current = left;
                }else{
//此时已经是堆了，无需继续向下调整
break;
                }
            }else{
//左右节点都不存在,已经调整到底了
break;
            }
        }
    }