1.直接插入排序
思想：每一趟将一个待排的元素作为关键字，按照其关键字的大小插入到已经排好序的部分序列的适当位置上，直到插入完成。
实现:
public static void insertSort(int arr[]){
for (int i=1;i<arr.length;i++){ //从第二个值开始插
int value=arr[i]; //待插入的元素
int post=i;
while(post>0 && arr[post-1]>value){
arr[post]=arr[post-1];
post--;
}
arr[post]=value; //找到其插入位置
}
}
2.冒泡排序
思想： 是一系列交换动作完成的。
第一趟：第一个元素跟第二个比较，若果前者大于后者，两者位置交换，一次两两比较，直到最大的元素到最后的位置。
第二趟：第一个元素跟第二个比较，一直比较到n-1
实现:
//冒泡排序基础版
public static void bubbleSort1(int[] arr,int n){
int i,j;
for(i=n-1;i>0;i--){ //外层循环比较n-1次:第一次确定最后一个位置上的值，最后确定第二个位置上的值即可
for (j=0;j<i;j++){ //内层循环
if(arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
//冒泡排序改进版
public static void bubbleSort2(int[] arr,int n){
int i,j;
for(i=n-1;i>0;i--){
int flag=0;
for (j=0;j<i;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
flag=1; //若发生交换，则设标记为1
}
}
if (flag==0)
{return;}
}
}
3.选择排序
思想：
选择排序也是一种交换排序，和冒泡排序有一定的相似度，可以认为是冒泡的一种改进。
1. 在未排序的序列中找到最大或最小值，放到排序序列的起始位置
2. 从剩余未排序的元素中继续寻找最大（小）元素，放到已排序列的末尾。
3. 重复第二步，直到所有的元素均排序完毕。
实现：
public class SelectSort {
//使序列递增
public static void selectSort(int[] arr,int n){
int temp, min = 0;
if((arr==null)||(arr.length==0))
return;
for (int i = 0; i < n; i++) {
min = i;//无序区的最小数据数组下标
// 循环查找最小值
for (int j = i + 1; j < n; j++) { //在无序区中找到最小数据并保存其数组下标
if (arr[min] > arr[j]) {
min = j;
}
}
if (min != i) {
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
}
4.快速排序
思想：
1. 定义两个指针，分别指向数组的第一个元素和最后一个元素。
2. 第一趟以第一个元素为基准，从后向前扫描，直到遇到比基准小的值，交换两个指针上的值； 换方向从前向后扫描，直到遇到比基准大的值，交换两个指针上的值。
当首尾两个指针重合时，指针指向的值为基准；将其指向的值与基准互换。
3. 分别递归对前后两部分进行快排。
实现：
public class QuickSort{
public static void quickSort3(int[] arr,int low,int high){
if (low>high){
return;
}
int i,j,temp;
i=low;
j=high;
temp=arr[low];
while (i!=j){
while(i<j&&temp<=arr[j]) {j--;}
if (i<j){
arr[i]=arr[j];
i++;
}
while (i<j&&temp>=arr[i]){i++;}
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=temp;
quickSort(arr,low,i-1);
quickSort(arr,i+1,high);
}
}
5.归并排序
思想：将两个有序的数组合并为一个有序的数组；分治法，利用递归将数组分解为长度的1的数组，再将数组合并为有序的。
实现：
public class Merge_Sort {
public static void sort(int[] a,int left,int right){
int mid = (left+right)/2;
if(left<right){
sort(a,left,mid);
sort(a,mid+1,right);
//左右归并
merge(a,left,mid,right);
}
}
//把两个有序的合并为一个有序的
public static void merge(int[] arr,int l,int m,int r){
int[] temp = new int [r-l+1];
int i=l;
int j=m+1;
int k=0;
//把两者较小的 添加到新数组中
while (i<=m &&j<=r){
if (arr[i]<arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
//把左边剩余的数添加到新数组中
while(i<=m){
temp[k++]=arr[i++];
}
//把右边剩余的数添加到新数组中
while(j<=r){
temp[k++]=arr[j++];
}
//把新数组中 的数在赋给原数组
for(int x=0;x<temp.length;x++){
arr[l+x]=temp[x];
//System.out.print(arr[l+x]+" ");
}
}
}
6.堆排序
思想：(以大顶堆为例)
堆调整（heapify）：父节点的值最大，若果不是，就交换，并递归对交换后的节点进行调整。保证堆顶元素最大。
建堆：从最后一个非叶节点向上做调整。
堆排序（降序）：把大顶堆的根节点和最后一个节点交换，保证最大的节点在最后一个位置上。因为交换完已经不是一个堆了，所以需要再次从根节点做heapify.
第二趟，把当前各节点和当前最后一个位置上的节点交换，依次.....
实现：
public class Heap_Big {
//对每个节点的左右字节点和自身建立一个大顶堆
public static void heapify(int[] tree, int n, int i){
if (i>=n)
return ;
int c1 = 2 * i + 1 ;
int c2 = 2 * i + 2 ;
int max = i ;
if (c1 < n && tree[max]< tree[c1] )
max = c1 ;
if (c2 < n && tree[max]< tree[c2] )
max = c2 ;
if (max != i){
swap(tree, max, i);
heapify(tree, n, max);//递归对交换完以后的节点建立一个大顶堆
}
}
private static void swap(int[] tree, int i, int j) {
int temp = tree[i];
tree[i] = tree[j];
tree[j] = temp;
}
//对一组数建立一个大顶堆
public static void build_heap(int[] tree, int n){
int last_node=n-1;
int parent=(last_node-1)/2;
for (int i=parent;i>=0; i--){
heapify(tree, n, i);
}
}
//堆排序：把大顶堆的根节点和最后一个节点交换，保证最大的节点在最后一个位置上，
//因为交换完已经不是一个堆了，所以需要再次从根节点做heapify.第二趟，把当前各节点和当前最后一个位置上的节点交换，
public static void heap_sort(int [] tree, int n){
build_heap(tree,n);
for (int i=n-1;i>=0;i--){
swap(tree,i,0);
heapify(tree,i,0);
}
}
public static void main(String[] args) {
int[] array = {4,10,5,3,1,2};
int n=array.length;
heapify(array,n,0);
System.out.println("heapify的过程:");
for (int i=0;i<n;i++){
System.out.print(array[i]+" ");
}
System.out.println();
build_heap(array,n);
System.out.println("建堆的过程:");
for (int i=0;i<n;i++){
System.out.print(array[i]+" ");
}
System.out.println();
heap_sort(array,n);
System.out.println("堆排序的结果");
for (int i=0;i<n;i++){
System.out.print(array[i]+" ");
}
}
}
//小顶堆
public class Heap_Small {
//小顶堆调整的过程 public static void heapify2(int[] tree,int n, int i){ if(i>=n) return; int c1=2 * i +1; int c2=2*i+2; int min=i; if (c1<n && tree[c1]<tree[min]) min=c1; if (c2<n && tree[c2]<tree[min]) min=c2; if (min != i){ swap(tree,min,i); heapify2(tree,n,min); } } private static void swap(int[] tree, int i, int j) { int temp=tree[i]; tree[i]=tree[j]; tree[j]=temp; }
//从一组数中建小顶堆 public static void build_heap2(int[] tree,int n){ int lastnode=n-1; int par=(lastnode-1)/2; //从最后一个非叶节点开始调整 for(int i=par;i>=0;i--){ heapify2(tree,n,i); } } public static void heap_sort_small(int[] tree,int n){ build_heap2(tree,n); //交换堆顶和当前堆的最后一个元素，确保最小的元素在最后一个位置上，由于交换以后的结果就不是小顶堆了，所以要进行heapify //第二趟，在交换当前堆顶元素和最后一个元素，heapify for (int i=n-1;i>=0;i--){ swap(tree,0,i); heapify2(tree,i,0); } }
//小顶堆的插入 public static void heapInsert(int[] tree,int n,int num){ int i,j; i=n;j=(n-1)/2; while(j>=0 && i!=0){ if (tree[j]<=num) break; tree[i]=tree[j]; i=j; j=(i-1)/2; } tree[i]=num; }
//测试 public static void main(String[] args) { int[] array = {10,4,5,3,1,2}; int n=array.length; build_heap2(array,n); //heapify2(array,n,0); System.out.println("建堆的过程:");//建好的堆为：1 3 2 10 4 5 for (int i=0;i<n;i++){ System.out.print(array[i]+" "); } System.out.println(); heap_sort_small(array,n); //heapify2(array,n,0); System.out.println("堆排序的结果为");//建好的堆为：1 3 2 10 4 5 for (int i=0;i<n;i++){ System.out.print(array[i]+" "); } System.out.println(); int[] array2 = {10 ,30 ,20 ,100 ,40 ,50,14}; heapInsert(array2,6,14); System.out.println("小顶堆中插入一个数");//建好的堆为：1 3 2 10 4 5 for (int i=0;i<array2.length;i++){ System.out.print(array2[i]+" "); } } }
7.希尔排序
思想：
1.希尔排序是对插入排序的改进。
2. 把较大的数据集合先分为若干小组（逻辑上分组），然后对每一个小组分别进行插入排序。
实现:
public class ShellSort {
public static void main(String[] args) {
int[] arr={3,5,2,7,4,8,3,9};
shellSort(arr);
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static void shellSort(int [] arr){
int n=arr.length;
//分组，开始时增量为数组长度的一半
for(int gap=n/2;gap>0;gap/=2){
//对分组进行插入
for(int i=gap;i<n;i++){
//将arr[i] 插入正确的位置上
insert(arr,gap,i);
}
}
}
private static void insert(int[] arr,int gap,int i){
int value=arr[i];
int j;
for( j=i-gap; j>=0 && value<arr[j];j-=gap ){
arr[j+gap]=arr[j];
}
arr[j+gap]=value;
}
}
8.基数排序
9.桶排序
原文：https://www.cnblogs.com/yaogungeduo/p/11244277.html