[黑马程序员济南] JAVA常见的排序算法

在面试的过程中,经常被问到常用的排序算法有哪些,但是大部分开发人员都是蒙圈的.下面给大家介绍几种常用的排序算法.

1.冒泡排序

基本思路:

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

3.针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。

实现的示例代码:

public class Demo1 {

  public static void main(String[] args) {

       int[] arr= {25,65,14,16,15,4,8,61,51,54,51};

        for (int i = 0; i < arr.length; i++) {    

      for (int j = 0; j < arr.length  -1- i; j++) {  

            if (arr[j] > arr[j+1]) {

            int temp = arr[j];  

            arr[j] = arr[j + 1];

            arr[j +1] = temp;

            }

         }

        }

2.选择排序

一趟在 n - i + 1(n = 1,2,3...,n - 1)个记录中选取关键字最小的记录作为有序序列的第i个记录。

关键点：比较两个记录的大小，如果反序，记录下下标，知道一趟比较完毕，让后将原来第i个记录与最后记录的小标的记录交换。

public class SelectionSort {    public static void main(String[] args) {

       int[] arr={1,3,2,45,65,33,12};        System.out.println("交换之前：");   

     for(int num:arr){   

        System.out.print(num+" ");   

    }        

        //选择排序的优化        

for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序

            int k = i;

           for(int j = k + 1; j < arr.length; j++){

// 选最小的记录

                if(arr[j] < arr[k]){

                     k = j; //记下目前找到的最小值所在的位置

              

  }        

    }   

         //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换

   if(i != k){

  //交换a和a[k]

               int temp = arr;

               arr = arr[k];

               arr[k] = temp;  

          }  

          }      

  System.out.println();  

  

    System.out.println("交换后：");

       for(int num:arr){  

          System.out.print(num+" ");   

     }

   }

}
3.插入法排序

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

public static void InsertSort(int[] arr){

    int i, j;

   int n = arr.Length;

    int target;     //假定第一个元素被放到了正确的位置上    //这样，仅需遍历1 - n-1   

for (i = 1; i < n; i++)    {  

      j = i;

   

   target = arr;   

      while (j > 0 && target < arr[j - 1])        {

           arr[j] = arr[j - 1];     

           j--;   

   

  }   

   

  arr[j] = target;  

  }}

4.希尔法排序

现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有
序”后，最后在对所有元素进行一次直接插入排序.

public void sort(int[] arr) {       

// i表示希尔排序中的第n/2+1个元素（或者n/4+1）

        // j表示希尔排序中从0到n/2的元素（n/4）

        // r表示希尔排序中n/2+1或者n/4+1的值        

      int i, j, r, tmp;         // 划组排序

        for(r = arr.length / 2; r >= 1; r = r / 2) {

            for(i = r; i < arr.length; i++) {  

               tmp = arr;  

               j = i - r;    // 一轮排序

               while(j >= 0 && tmp < arr[j]) {  

                  arr[j+r] = arr[j];

                    j -= r;   

            }   

            arr[j+r] = tmp;  

           }

             System.out.println(i + ":" + Arrays.toString(arr));

         }

    }

5.数组排序
其实数组排序比较简单,在java.utils.Arrays类中有一个静态方法sort,可以用这个类的sort方法对数组进行排序
示例代码:public class Test{

public static void main(String[] args){

//需要排序的数组,目前是按照升序排序

int a[] = new int[5];

a[0] = 3;

a[1] = 4;

a[2] = 1;

a[3] = 5;

a[4] = 2;

java.util.Arrays.sort(a);

}}

【黑马程序员济南】小鲁哥哥全学科技术整合帖（一贴在手！天下我有！）

如果你想了解更多黑马课程，如果你想加入黑马这个大家庭学习先进技术，光交天下好友，那就快来吧！

     黑马程序员济南中心联系电话：0531-55696830

[黑马程序员济南] JAVA常见的排序算法

在面试的过程中,经常被问到常用的排序算法有哪些,但是大部分开发人员都是蒙圈的.下面给大家介绍几种常用的排序算法.

1.冒泡排序

基本思路:

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

3.针对所有的元素重复以上的步骤，直到没有任何一对数字需要比较。

实现的示例代码:

public class Demo1 {

  public static void main(String[] args) {

       int[] arr= {25,65,14,16,15,4,8,61,51,54,51};

        for (int i = 0; i < arr.length; i++) {    

      for (int j = 0; j < arr.length  -1- i; j++) {  

            if (arr[j] > arr[j+1]) {

            int temp = arr[j];  

            arr[j] = arr[j + 1];

            arr[j +1] = temp;

            }

         }

        }

2.选择排序

一趟在 n - i + 1(n = 1,2,3...,n - 1)个记录中选取关键字最小的记录作为有序序列的第i个记录。

关键点：比较两个记录的大小，如果反序，记录下下标，知道一趟比较完毕，让后将原来第i个记录与最后记录的小标的记录交换。

public class SelectionSort {    public static void main(String[] args) {

       int[] arr={1,3,2,45,65,33,12};        System.out.println("交换之前：");   

     for(int num:arr){   

        System.out.print(num+" ");   

    }        

        //选择排序的优化        

for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序

            int k = i;

           for(int j = k + 1; j < arr.length; j++){

// 选最小的记录

                if(arr[j] < arr[k]){

                     k = j; //记下目前找到的最小值所在的位置

              

  }        

    }   

         //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换

   if(i != k){

  //交换a和a[k]

               int temp = arr;

               arr = arr[k];

               arr[k] = temp;  

          }  

          }      

  System.out.println();  

  

    System.out.println("交换后：");

       for(int num:arr){  

          System.out.print(num+" ");   

     }

   }

}
3.插入法排序

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

public static void InsertSort(int[] arr){

    int i, j;

   int n = arr.Length;

    int target;     //假定第一个元素被放到了正确的位置上    //这样，仅需遍历1 - n-1   

for (i = 1; i < n; i++)    {  

      j = i;

   

   target = arr;   

      while (j > 0 && target < arr[j - 1])        {

           arr[j] = arr[j - 1];     

           j--;   

   

  }   

   

  arr[j] = target;  

  }}

4.希尔法排序

现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有
序”后，最后在对所有元素进行一次直接插入排序.

public void sort(int[] arr) {       

// i表示希尔排序中的第n/2+1个元素（或者n/4+1）

        // j表示希尔排序中从0到n/2的元素（n/4）

        // r表示希尔排序中n/2+1或者n/4+1的值        

      int i, j, r, tmp;         // 划组排序

        for(r = arr.length / 2; r >= 1; r = r / 2) {

            for(i = r; i < arr.length; i++) {  

               tmp = arr;  

               j = i - r;    // 一轮排序

               while(j >= 0 && tmp < arr[j]) {  

                  arr[j+r] = arr[j];

                    j -= r;   

            }   

            arr[j+r] = tmp;  

           }

             System.out.println(i + ":" + Arrays.toString(arr));

         }

    }

5.数组排序
其实数组排序比较简单,在java.utils.Arrays类中有一个静态方法sort,可以用这个类的sort方法对数组进行排序
示例代码:public class Test{

public static void main(String[] args){

//需要排序的数组,目前是按照升序排序

int a[] = new int[5];

a[0] = 3;

a[1] = 4;

a[2] = 1;

a[3] = 5;

a[4] = 2;

java.util.Arrays.sort(a);

}}

【黑马程序员济南】小鲁哥哥全学科技术整合帖（一贴在手！天下我有！）

如果你想了解更多黑马课程，如果你想加入黑马这个大家庭学习先进技术，光交天下好友，那就快来吧！

     黑马程序员济南中心联系电话：0531-55696830