简单插入排序
package lxq.java.sort;
public class InsertSort {
public static void insertSort(Integer[] arr){
int i,j;
for(i=2;i<=arr.length-1;i++){
//要插入 的元素小于前面最后一个元素，说明当然元素必须插入到前面合适的位置去
if(arr[i]<arr[i-1]){
arr[0]=arr[i];
//不需要加j>=1的判断，因为当arr[i]比前面的都小时，最后会比较arr[0]>arr[0]
for(j=i-1;arr[j]>arr[0];j--){
arr[j+1]=arr[j];
}
arr[j+1]=arr[0];
}
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
insertSort(arr);
System.out.println("插入排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
选择排序
package lxq.java.sort;
//冒泡排序每一次从剩下所有的元素中找出最小的比较
public class SelectionSort {
public static void selectionSort(Integer[] arr){
//imin记录最小值，index记录最小值的下标，tmp用于交换的临时变量
int i,j,imin,index,tmp;
for(i=1;i<arr.length-1;i++){
imin=arr[i];
index=i;
for(j=i+1;j<=arr.length-1;j++){
if(arr[j]<imin){
imin=arr[j];
index=j;
}
}
tmp=arr[i];
arr[i]=arr[index];
arr[index]=tmp;
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
selectionSort(arr);
System.out.println("选择排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
冒泡排序
package lxq.java.sort;
//冒泡排序每一次只是相邻的两个元素比较,注意j必须从大到小才能保证冒泡
public class BubbleSort {
public static void bubbleSort(Integer[] arr){
int i,j,tmp;
for(i=1;i<arr.length-1;i++){
for(j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
bubbleSort(arr);
System.out.println("冒泡排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
希尔排序
package lxq.java.sort;
//希尔排序的一趟排序类似与插入排序，只是增量不一样
public class ShellSort {
public static void shellSort(Integer[] arr,int dk){
int i,j;
for(i=dk+1;i<=arr.length-1;i++){
//要插入 的元素小于前面最后一个dk元素，说明当然元素必须插入到前面合适的位置去
if(arr[i]<arr[i-dk]){
arr[0]=arr[i];
for(j=i-dk;j>=1&&arr[j]>arr[0];j-=dk){
arr[j+dk]=arr[j];
}
arr[j+dk]=arr[0];
}
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
Integer[] dlta=new Integer[]{5,3,1};//增量
for(int i=0;i<dlta.length;i++){
shellSort(arr,dlta[i]);
}
System.out.println("希尔排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
快速排序
package lxq.java.sort;
public class QuickSort {
public static int partition(Integer[] arr,int low,int high){
arr[0]=arr[low];
while(low<high){
while(low<high&&arr[high]>=arr[0]){
high--;
}
arr[low]=arr[high];
while(low<high&&arr[low]<=arr[0]){
low++;
}
arr[high]=arr[low];
}
arr[low]=arr[0];
return low;
}
public static void quickSort(Integer[] arr,int low,int high){
if(low<high){
int parloc=partition(arr,low,high);
quickSort(arr,low,parloc-1);
quickSort(arr,parloc+1,high);
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
quickSort(arr,1,arr.length-1);
System.out.println("快速排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
归并排序
package lxq.java.sort;
public class MergeSort {
public static void merge(Integer[] arr,int s,int m,int t){
int i,j,k;
Integer[] res=new Integer[t-s+1];//根据arr中要合并的长度申请临时数组的长度
for(i=s,j=m+1,k=0;i<=m&&j<=t;k++){
if(arr[i]<arr[j]){
res[k]=arr[i++];
}
else{
res[k]=arr[j++];
}
}
while(i<=m){
res[k]=arr[i++];
k++;
}
while(j<=t){
res[k]=arr[j++];
k++;
}
for(k=s;k<=t;k++){//临时数组存放的数据是从0开始的哦
arr[k]=res[k-s];
}
}
public static void mergeSort(Integer[] arr,int s,int t){
if(s==t){
return;
}
else{
int m=(s+t)/2;
mergeSort(arr,s,m);
mergeSort(arr,m+1,t);
merge(arr,s,m,t);
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
mergeSort(arr,1,arr.length-1);
System.out.println("归并排序执行结果如下：");
for(int i=1;i<=arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
堆排序
package lxq.java.sort;
public class HeapSort {
public static void heapAdjust(Integer[] arr,int adjustIndex,int length){
int adjustValue=arr[adjustIndex];
int i;
for(i=2*adjustIndex;i<=length;i*=2){//沿值较小的孩子节点向下筛选
if(i+1<=length&&arr[i+1]<arr[i]) i++;
if(adjustValue<=arr[i]) break;//已经符合则退出
arr[adjustIndex]=arr[i];//将孩子节点的小值赋给父节点，孩子节点的值暂时不变，等到下次孩子节点的孩子节点赋值给它或等到筛选结束时赋值给它
adjustIndex=i;
}
arr[adjustIndex]=adjustValue;//在最后的位置上赋值最开始要筛选的值，就完成本次筛选
}
public static void heapSort(Integer[] arr){
for(int i=(arr.length-1)/2;i>=1;i--){//把数组arr[1,arr.length-1]建成小顶堆
heapAdjust(arr,i,arr.length-1);
}
for(int i=arr.length-1;i>1;i--){
int tmp=arr[1];//将堆顶记录和当前arr[1,i]中最后一个记录相互交换
arr[1]=arr[i];
arr[i]=tmp;
heapAdjust(arr,1,i-1);//将arr[1,i-1]重新调整为小顶堆，也即对堆顶元素进行一次筛选
}
}
public static void main(String[] args) {
//0号位置留作哨兵之用，注意只是数组最大下标为length-1
Integer[] arr=new Integer[]{null,49,38,65,97,76,13,27,49,55,04};
heapSort(arr);
System.out.println("堆排序执行结果如下：");
for(int i=arr.length-1;i>=1;i--){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}