韩顺平 java笔记 第17讲 第18讲 排序 查找

时间:2022-10-28 21:03:58

1.排序分类

  (1)内部排序

    交换式排序  选择式排序 (选择排序法、堆排序法)插入式排序

  (2)外部排序

    合并排序 直接合并排序法

2.交换式排序

  (1)冒泡排序

    79  56  90  4  32  27  16  88  35 

    90  79  56  88  4  32  27  16  35 

    90  88  79  56  35  4  32  27  16

    90  88  79  56  35  32  4  27  16

              90  88  79  56  35  32  27  4  16

    90  88  79  56  35  32  27  16  4

              90  88  79  56  35  32   27  16  4

    public class Demo{

      public static void main(String[] args){

        int arr[] = {1,6,0,-1,9,-100,90};

        Bubble bubble = new Bubble();

        bubble.sort(arr);

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

          System.out.println(arr[i] + "  ");

        }

      }    

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

          System.out.print(arr[j] + "  ");

      }

    }

    class Bubble{

      public void Sort(int arr[]){

        int temp = 0;

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

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

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

               temp = arr[j];

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

               arr[j+1] = temp;

            }

          }

        }

      }

    }

  (2)快速排序法

    基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的数据都比另外一部分的所有数据小,然后按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行。

   class QuickSort{

    public void sort(int left,int right,int[] array){

      int l = left;

      int r = right;

      int pivot = array[(left+right)/2];

      int temp= 0;

      while(l<r){

        while(array[1] < pivot)  l++;

        while(array[r] > pivot) r--;

        if(l>=r) break;

        temp = array[1];

        array[1] = array[r];

        array[r] = temp;

        if(array[1] == pivot)  --r;

        if(array[r] == pivot)  ++l;

      }

      if (l==r){

        l++;r--;

      }

      if(left < r) sort(left,r,array);

      if(right >1) sort(l,right,array);

    }

   }

3.选择式式排序

  8  3  2  1  7  4  6  5 

  1  3  2  8  7  4  6  5

  1  2  3  8  7  4  6  5

  1  2  3  8  7  4  6  5

  1  2  3  4  8  7  6  5

  1  2  3  4  7  8  6  5

  1  2  3  4  5  8  6  7

  1  2  3  4  5  6  8  7

  1  2  3  4  5  6  7  8

  Select select = new Select();

  select.sort(arr1);

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

    System.out.println(arr1[i] + "  ");

  }

  class Select{

    public void Sort(int arr[]){

      int temp = 0;

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

        int min = arr[j];

        int minIndex = j;

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

          if(min > arr[k]){

            min = arr[k];

            minIndex = k;

          }

        }

        temp =arr[j];

        arr[j] = arr[minIndex];

        arr[minIndex] = temp;

      }

    }

4.插入式排序

  (1)插入排序法

   基本思想:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含n-1个元素,排序过程中,每次从无序表中取出第一个元素,把他的排序码依次与有序表元素的排序码进行比较,将他插入到有序表中的适当位置,使之成为新的有序表。

  17  3  25  14  20  9

  3  17  25  14  20  9

  3  17  25  14  20  9

  3  14  17  25  20  9

  3  14  17  20  25  9

  3   9  14  17  20  25

  class InsertSort{

    public void sort(int arr[]){

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

        int insertVal = arr[i];

        int index = i-1;

        while(index>=0&&insertVal < arr[index]){

          arr[index + 1]  = arr[index];

          index --;

        }

        arr[index + 1] = insertVal;

      }

    }

  }

  (2)希尔排序法

  (3)二叉树排序法

5.查找

  (1)顺序查找

  (2)二分查找

    思路:找到数组的中间数(midVal),和你要查找的数finalVal进行比较,如果midVal>findVal,则说明findVal在数的左边,就把该数组二分。

  class BinaryFind{

    public void find (int leftIndex,int rightIndex,int val,int arr[]){

      int midIndex = (rightIndex+leftIndex)/2;

      int midVal = arr[midIndex];

      if(rightIndex >= leftIndex){

        if(midVal > val){

          find (leftIndex,midIndex-1,val,arr);

        }else if (midVal <val){

          find (midIndex +1,rightIndex,val,arr);

        }else if (midVal == val){

          System.out.println(“找到下标”+midIndex);

        }

      }

    }

   }