七大排序java实现

一.冒泡排序:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
package Exercise;

import java.util.Arrays;

public class TestBubbleSort {
    public static void main(String[] args) {
        int[] a={3,1,6,2,9,0,7,4,5,8};
        int temp=0;
        for(int i=0;i<a.length-1;i++){
            //因为已经排好了i个了,所以只需要排length-i的数,-1是因为只需要排到倒数第二个,否则j+1会产生数组越界
            for(int j=0;j<a.length-1-i;j++){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
            System.out.println("第"+i+"次排序的结果"+Arrays.toString(a));
        }
    }
}

运行结果:

 可以观察到,在第四次该数组已经排好序,没有必要再进行后面的排序,所以应给予优化;可以采取设置一个flag变量,如果经历了交换,就将它设置为false

 for(int i=0;i<a.length-1;i++){
            //因为已经排好了i个了,所以只需要排length-i的数,-1是因为只需要排到倒数第二个,否则j+1会产生数组越界
            boolean flag=true;
            for(int j=0;j<a.length-1-i;j++){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                   flag=false;
                }
            }
            if(flag){
                System.out.println("排序结束!");
                break;
            }
            System.out.println("第"+i+"次排序的结果"+Arrays.toString(a));
        }

优化后的结果:

注:加入标志flag,如果产生了交换,说明该组数据还是乱序;如果flag已经为true,说明整个数组已经排好序,无需再进入下一次排序。

二:直接插入排序

  1. 从第一个元素开始,该元素可以认为已经被排
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5
package Exercise;
import java.util.Arrays;

/**
 * 从第一个值开始向前面插入,后面的数字插入时,前面的数字一定已经排好序了。找一个位置将这个数放入正确的位置
 */
public class TestInsertSort {
    public static void main(String[] args) {
        int[] a={19,3,56,8,55,89,1};
        for(int i=0;i<a.length;i++){
            //j从后往前判断,如果前面的数比它小,则交换,继续向前判断;
            for(int j=i;j>0;j--){
                if(a[j]<a[j-1]){
                    int temp=a[j];
                    a[j]=a[j-1];
                    a[j-1]=temp;
                }else {  //如果后面的比前面的值大,则跳出内层for循环,进行下一个数的判断
                    break;
                }
            }
            System.out.println("每"+i+"次的插入结果"+Arrays.toString(a));//因为第0次只有一个数,不能参与排序,所以依然是原数组
        }
        System.out.println(Arrays.toString(a));
    }
}

 注:i控制整个数组的每一个数,j控制每一个数与该数之前的数,依次比较。所以内层循环j变量的起始应该是i,最小值是1>0,否则会数组越界; break的作用是跳出本层循环。外层如果还有循环,是不能跳出外层循环范围的(所以如果该数比前面的数都大,应该由i控制进入下一个数的向前比较)。

 三:快速排序

  1. 从数列中挑出一个元素,称为"基准"(pivot)。
  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
package Exercise;
import java.util.Arrays;
public class QuikSort {;
    public static void main(String[] args) {
        int[] a={2,5,7,1,3,9,4,8};
        qSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void qSort(int a[]){
            qSort(a,0,a.length-1);
    }
    public static void qSort(int[] a,int left,int right){
     if(left>=right){
         return;
     }
     int pivot=a[(left+right)/2];
     int index=partiton(a,left,right,pivot);
        System.out.println("left:"+left+" right:"+right+" 下标是:"+index+" 基准是:"+pivot+" "+ Arrays.toString(a));
     qSort(a,left,index-1);
     qSort(a,index,right);
    }
    public static int partiton(int[] a,int left,int right,int pivot){
        while (left<=right){
            while (a[left]<pivot){
                left++;
            }
            while (a[right]>pivot){
                right--;
            }
            if (left<=right){
                swap(a,left,right);
                left++;right--;
            }
        }
        return left;
    }
    public static void swap(int[] a,int l,int r){
        int temp=a[l];
        a[l]=a[r];
        a[r]=temp;
    }

}

 注:函数的调用过程;每次基准的划分pivot以及下标的确认; 递归函数的相互调用。

 四:简单选择排序

  1. 从未排序序列中,每次以第一个元素为最小元素
  2. 继续在之后的序列中依次比较,如果有小于如果最小元素不是未排序序列的第一个元素,将其和未排序序列第一个元素互换
  3. 重复1、2步,直到排序结束。
package Exercise;
import java.util.Arrays;
public class SelectSort {
    public static void main(String[] args) {
        int[] a={2,5,7,1,3,9,4,8};
        selectSort(a);
        System.out.println("排好序的数组为:"+Arrays.toString(a));
    }
    public static void selectSort(int[] a){
        for(int i=0;i<a.length;i++){
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[i]){
                    swap(a,i,j);
                }
            }
            System.out.println("每"+(i+1)+"次的选择之后的结果:"+Arrays.toString(a));
        }
    }
    public static void swap(int[] a,int l,int r){
        int temp=a[l];
        a[l]=a[r];
        a[r]=temp;
    }
}

注:i控制外层循环,j控制i以后的数组中找出最小的元素。

五:希尔排序

  1. 选择一个增量序列 gap;
  2. 按增量序列个数,对序列进行 gap/2直到=1 趟排序;
  3. 每趟排序,根据对应的增量,将待排序列分割成若干长度子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
package Exercise;

import java.util.Arrays;
public class ShellSort {
    public static void main(String[] args) {
        int[] a={8,9,1,7,2,3,5,4,6,0};
        shellSort(a);
    }
    public static void shellSort(int[] a){
        int count=0;
        for(int gap=a.length/2;gap>0;gap=gap/2) {
            for (int i = gap; i < a.length; i++) {
                for (int j = i-gap; j >= 0; j = j - gap) {
                    if (a[j] > a[j+gap]) {
                        int temp=a[j];
                        a[j]=a[j+gap];
                        a[j+gap]=temp;
                    }
                }
            }
//            for (int i = 0; i < gap; i++) {
//                for (int j = i+gap; j <a.length; j = j + gap) {
//                    if (a[i] > a[j]) {
//                        int temp=a[i];
//                        a[i]=a[j];
//                        a[j]=temp;
//                    }
//                }
//            }
            System.out.println("第"+(++count)+"次希尔排序后的结果:"+ Arrays.toString(a));
        }
    }

为什么不能应用注释掉的方法,从前向后依次遍历呢?

开始没有意识到后面要用直接插入排序,所以想的是从前往后也可以!应该根据冒泡排序的思想,从后往前找比它小的,交换数据。

 注:希尔排序是为了解决简单插入排序中,有最小的一个数在最后一位的情况,那么就需要一直向前移动;所以采用先分组,将整体比较小的元素向前移动,然后直到gap=1,再借助直接插入排序提高效率。gap控制每次分组,组的个数。

六:归并排序

先写出当两个部分数组有序的情况,再用递归写出两个有序的情况。

package Exercise;
import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        int[] a={1,3,5,6,2,7,8,9,65,78,79};
        System.out.println("原数组:"+Arrays.toString(a));
        merge(a,0,3,a.length-1);
        System.out.println("排序后的数组为:"+Arrays.toString(a));
    }
    public static void merge(int[] a,int left,int middle,int right){
        int[] temp=new int[right-left+1];
        int i=left;
        int j=middle+1;
        int index=0;
        while (i<=middle&&j<=right){
            if(a[i]<a[j]){
                temp[index]=a[i];
                i++;
            }else {
                temp[index]=a[j];
                j++;
            }
            index++;
        }
        while (i<=middle){
            temp[index]=a[i];
            i++;index++;
        }
        while (j<=right){
            temp[index]=a[j];
            j++;index++;
        }
        for(int k=0;k<temp.length;k++){
            a[k]=temp[k];
        }
    }
}

 用递归算法后的合并排序:

package Exercise;
/**
 * 2020/1/11  合并排序的递归
 */

import java.util.Arrays;
public class MergeSort2 {
    public static void main(String[] args) {
        int[] a1={2,6,5,3,8,1};
        System.out.println("原数组:"+Arrays.toString(a1));
        sort(a1,0,a1.length-1);
        System.out.println("排序后的数组为:"+Arrays.toString(a1));
    }
    public static void sort(int[] a,int left,int right){
        if(left==right)return;
        int middle=(left+right)/2;
        sort(a,left,middle);
        sort(a,middle+1,right);
        merge(a,left,middle+1,right);
    }
    public static void merge(int[] a,int leftPtr,int rightPtr,int rightBound){
        int mid=rightPtr-1;
        int[] temp=new int[rightBound-leftPtr+1];
        int i=leftPtr;
        int j=rightPtr;
        int index=0;
        while (i<=mid&&j<=rightBound){
            temp[index++]=a[i]<=a[j] ? a[i++]:a[j++];
        }
        while (i<=mid){
            temp[index++]=a[i++];
           // i++;index++;
        }
        while (j<=rightBound){
            temp[index++]=a[j++];
            //j++;index++;
        }
        for(int k=0;k<temp.length;k++){
            a[k+leftPtr]=temp[k];
        }
    }
}

注:把排好的临时数组赋给a时,要从leftPtr开始,即已经排好的数组开始覆盖;

疑惑点,debug之后开始明白:

七.堆排序

                  1.构建大根堆adjustHeap,对构建成的整个数组进行最后一位与当前最大的进行交换

                  2.具体构建大根堆的过程,找到最后一个非叶子节点,比较它的孩子节点与它的值大小,将比较大节点作为父子节点,直到遍历到根节点,

                          即为目前数组最大的值,再返回heapSotr交换的操作。

                   3.重复1,2步骤,直到遍历到目前数组中只剩一个元素

package Exercise;
/**
 * 2020/1/12
 * 堆排序
 */

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] a={4,6,8,5,9};
        heapSort(a);
    }
    public static void heapSort(int[] a){
        adjustHeap(a,1,a.length);
        System.out.println("第一次调整:"+Arrays.toString(a));//4 9 8 5 6
        adjustHeap(a,0,a.length);
        System.out.println("第二次调整: "+Arrays.toString(a));//9 6 8 5 4
    }
    public static void adjustHeap(int[] a,int i,int length){
        int temp=a[i];
        for(int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length && a[k]<a[k+1]){
                k++;
            }
            //如果叶子节点大于父节点
            if(a[k]>temp){
                a[i]=a[k];
                i=k;
            }else {
                break;//如果父节点本来就比孩子节点大,直接跳出,进行下一个父节点的比较
            }
        }
        a[i]=temp;//将temp放到调整后的位置
    }
}

 对heapSort优化递归,进行整个树的调整

 public static void heapSort(int[] a){
        int temp=0;
//        adjustHeap(a,1,a.length);
//        System.out.println("第一次调整:"+Arrays.toString(a));//4 9 8 5 6
//        adjustHeap(a,0,a.length);
//        System.out.println("第二次调整: "+Arrays.toString(a));//9 6 8 5 4
//此时i是最后一个非叶子节点 for(int i=a.length/2-1;i>=0;i--){ adjustHeap(a,i,a.length); } //最大值跟最后一个数交换 for(int j=a.length-1;j>0;j--) { //调整大根堆之后,进行交换 temp=a[j]; a[j]=a[0]; a[0]=temp; adjustHeap(a,0,j); } }

另一种方法:博客中看到了另一种更好理解的方法

package Exercise;
/**
* 2020/1/12
*/
import java.util.Arrays;
public class HeapSort2 {
public static void main(String[] args) {
int[] a={2,5,6,4,3,8,9,0};
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] a) {

for (int i = a.length - 1; i > 0; i--) {
max_heapify(a, i);
//堆顶元素(第一个元素)与Kn交换
int temp = a[0];
a[0] = a[i];
a[i] = temp;
}
}
/**
* 将数组堆化
* i = 第一个非叶子节点。从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
* @param a
* @param n
*/
public static void max_heapify(int[] a, int n) {
int child;
for (int i = (n - 1) / 2; i >= 0; i--) {
//左子节点位置
child = 2 * i + 1;
//右子节点存在且大于左子节点,child变成右子节点
if (child != n && a[child] < a[child + 1]) {
child++;
}
//交换父节点与左右子节点中的最大值
if (a[i] < a[child]) {
int temp = a[i];
a[i] = a[child];
a[child] = temp;
}
}
}
}

新加入了对每一次排序后的过程:

    public static void sort(int[] a) {
        int count=0;
        for (int i = a.length - 1; i > 0; i--) {
            max_heapify(a, i);
            //堆顶元素(第一个元素)与Kn交换
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            System.out.println("每"+(++count)+"次排序后的结果:"+Arrays.toString(a));
        }
    }

原文地址:https://www.cnblogs.com/laurarararararara/p/12171113.html