常用排序java实现

青旅半醒 2021-09-26 07:32 252阅读 0赞

# 排序算法复习 #

## 包括冒泡排序，快速排序，选择排序，插入排序，还有二分法查找 ##

### 为了方便，这里排序都用数组进行演示。 ###

package com.crazzy.sort;
    
    /** * Created by qqg on 2017/10/10. */
    public class Sort { 
        /** * 冒泡排序 + 优化 * 1.比较相邻的俩个元素，将大的放入后面。 * 2.循环 1 ，直到满意元素比较为止。 * 3.优化： a.每次循环完后，下一次循环可以 -1 ，因为后面的数已经是排序好的了，不需要在比较 * b.每次交换时，用一个标记 f 记录，若存在一次不需要交换，说明排序提前完成，可以结束排序 * @param number */
        public void bubbleSort(int []number){
            boolean f ;  //一旦有一次不用交换，说明已经排序好，不用在继续排序
            int count = 0; //排序次数
            for(int i=0;i<number.length;i++){
                f = true;
                for(int j=0;j<number.length - 1 - i;j++){
                    count ++;
                    if(number[j] > number[j+1]){
                        f = false;
                        //交换俩个数，不使用中间变量哦~
                        number[j] = number[j] + number[j+1] ;
                        number[j+1] = number[j] - number[j+1];
                        number[j] = number[j] - number[j+1];
                    }
                }
                //提前结束排序
                if(f)
                    break;
            }
            System.out.println("循环次数："+count);
        }
    
        /** * 快速排序 * 1.从数列中挑出一个元素，称为“基准” * 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 * 在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 * 3.递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。 * @param number */
        public void quickSort(int [] number,int start,int end){
            if(start < end){
                int base = number[start];
                int i = start, j = end;
                int temp;
                do{
                    while ((number[i] < base) && (i < end))
                        i++;
                    while ((number[j] > base) && (j > start))
                        j--;
                    if(i <= j){
                        temp = number[i];
                        number[i] = number[j];
                        number[j] = temp;
                        i++;
                        j--;
                    }
                }while (i <= j);
                if (start < j)
                    quickSort(number,start,j);
                if (end > i)
                    quickSort(number,i,end);
            }
        }
    
        /** * 选择排序 * 1.在未排序序列中找到最小元素，存放到排序序列的起始位置 * 2.再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。(就是上一步排序的末尾) * 3.以此类推，直到所有元素均排序完毕。 * @param number */
        public void selectSort(int []number){
            int temp;
            for(int i=0;i<number.length;i++){
                int k = i;
                for(int j=number.length-1;j > i;j--){
                    if(number[j] < number[k]) k = j;
                }
                temp = number[i];
                number[i] = number[k];
                number[k] = temp;
            }
        }
    
        /** *插入排序 * 1.从第一个元素开始，该元素可以认为已经被排序 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 5.将新元素插入到该位置中 * 6.重复步骤 2 * @param number */
        public void insertSort(int []number){
            int temp,j;
            for(int i = 1;i<number.length;i++){
                temp = number[i];
                for(j=i;j>0 && temp < number[j-1];j--) //查找插入的位置
                    number[j] = number[j-1];
                number[j] = temp;
            }
        }
        /** * 遍历数组 * @param number */
        public  void ergodic(int []number){
            for(int i = 0;i<number.length; i++){
                System.out.print(number[i]+"\t");
            }
        }
        /** * 二分法查找 * @param arr 查找数组 * @param num 查找元素 * @return 元素第一次出现的位置，若为 -1 表示没有找到 */
        public int binarySearch(int []arr ,int num){
            int start = 0;
            int end = arr.length - 1;
            while (start <= end){
                int min = (start + end)/2;
                if(arr[min] < num){
                    start = min + 1;
                }else if(arr[min] > num){
                    end = min - 1;
                }else {
                    return min;
                }
            }
            return -1;
        }
        public static void main(String[] args) {
            Sort sort = new Sort();
            int number[] = {
       3,4,5,4,2,3,33,1,2};
            sort.bubbleSort(number);
            //sort.quickSort(number,0,number.length-1);
            //sort.selectSort(number);
            sort.ergodic(number);
            int index = sort.binarySearch(number,2);
            System.out.println(index);
            //sort.insertSort(number);
        }
    }

# 还有归并排序，不是很清楚，就没有贴出来。先这样吧 #