JAVA排序算法笔记

文章目录

一、时间复杂度（判别排序算法优劣的尺度）
- 1、时间频度介绍和特点
- 2、时间复杂度计算
- 3、常见的时间复杂度
- - 1)、O(1)
  - 2）、O(logn)
  - 3）、O(n)
- 4、平均时间复杂度
二、冒泡排序
- 1、冒泡算法实现
- 2、冒泡算法优化
三、选择排序
- 1、选择排序基本思想
- 2、选择排序算法实现
4、插入排序
5、希尔排序
- 1、交换法
- 2、移位法

一、时间复杂度（判别排序算法优劣的尺度） 1、时间频度介绍和特点

时间频度：算法的时间复杂度与代码中语句执行次数成正比，例如计算1-100的和，代码：

int total=0;
int end=100;
for(int i =1;i<=end;i++){
	total+=i;
	
}

上述代码求和操作100次，再加上当i为101时仍需判断一次，所以时间复杂度T(n)=101

total = (1+end)*end/2;

上述代码时间复杂度T(n)=1
特点：时间复杂度公式可以忽略常数项和低次项

2、时间复杂度计算

1）一般情况下，程序中基本操作语句的重复执行次数是问题规模n的一个函数，称作T(n)。如果存在一个函数f(n)，当n趋向于无穷时，T(n)/f(n)的极限为一个不等于零的常数，则称f(n)是T(n)的同量级函数，用O(f(n))表示T(n)的时间复杂度。
2）T(n)不同时，时间复杂度可能相同
3）计算时间复杂度，只保留最高阶项并去除系数。

3、常见的时间复杂度

0(1) < O(logn) < O(n) < O(nlogn) < 0(n^2) < 0(n^3) < 0(2^n ) < O(n!) < O(n^n)

1)、O(1)

只要代码中没有循环等复杂结构，时间复杂度就为O(1)

2）、O(logn)

int i =1;
while(i 
3）、O(n) 
for(int i =0;i<100;i++){
	j=i
}
 
4、平均时间复杂度 
 
二、冒泡排序 
1、冒泡算法实现 
public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        int len = arr.length;
        int temp=0;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;iarr[i+1]){
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            System.out.println("第"+(j+1)+"次冒泡后数组为：");
            printArray(arr);
        }
    }
    //打印数组的方法
    public static void printArray(int[] arr){
        for (int i:arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }

}

 
代码结果运行如下：
 
 
时间复杂度T(n)=n^2
 
2、冒泡算法优化 
优化思路1：在冒泡过程中，有可能出现数组已经排序完成但仍然做无用的循环；
为避免这种情况，当冒泡过程中没有发生位置交换，则应该直接退出循环	
 
public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        int len = arr.length;
        int temp=0;
        boolean flag = false;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;iarr[i+1]){
                    flag = true;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            System.out.println("第"+(j+1)+"次冒泡后数组为：");
            printArray(arr);
            //如果flag仍未false说明一次也没有交换，可以直接退出循环
            if(!flag){
                break;
            }else{
                //重置flag方便下一次判断
                flag=false;
            }
        }




    }
    public static void printArray(int[] arr){
        for (int i:arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }

}
 
优化思路2：冒泡算法可以封装成一个方法，代码如下：
 
public class 冒泡 {
    public static void main(String[] args) {
        int arr[] = {-1,-2,9,5,3,1};
        System.out.println("冒泡前数组为：");
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("冒泡后数组为：");
        System.out.println(Arrays.toString(arr));
     
   }
    public static void bubbleSort(int[] arr){
        int len = arr.length;
        int temp=0;
        boolean flag = false;
        for (int j = 0; j < len-1; j++) {
            for(int i =0;iarr[i+1]){
                    flag = true;
                    temp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=temp;
                }
            }
            //如果flag仍未false说明一次也没有交换，可以直接退出循环
            if(!flag){
                break;
            }else{
                //重置flag方便下一次判断
                flag=false;
            }
        }
    }

}
 
测试时间复杂度，代码如下
 
        //创建一个长度80000的随机数组
        int arr[] =new int[80000];
        for (int i = 0; i <80000 ; i++) {
            arr[i]=(int)(Math.random()*1000000);
        }
        //获取排序前时间
        Date date1=new Date();
        SimpleDateFormat simpleDateFormat=new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
        String date1qstr=simpleDateFormat.format(date1);
        System.out.println("排序前时间："+date1qstr);
        //排序
        bubbleSort(arr);
        //获取排序后时间
        Date date2=new Date();
        String date2qstr=simpleDateFormat.format(date2);
        System.out.println("排序后时间为："+date2qstr);


 
三、选择排序 
1、选择排序基本思想 
选择排序属于内部排序，是在预选择的数组中，按指定规则挑选出某一元素，再依规定交换位置后达到排序的目的。
第一次挑选数组中最小的数和第一位交换
第二次挑选剩下数字中最小的数和第二位交换
第三次。。。。。。
依次类推直到最后一位
 
2、选择排序算法实现 
public class 选择 {
    public static void main(String[] args) {
        int[] arr={9,5,5,3,4,7};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void selectSort(int[] arr){
        int min =0;
        int temp=0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if(arr[temp]>=arr[j]){
                    temp=j;
                }
            }
            min=arr[temp];
            arr[temp]=arr[i];
            arr[i]=min;
        }
    }
}

 
4、插入排序 
把一个数组分为有序表和无序表，依次将无序表中的元素对有序表的元素比较，插入到合适的位置。
类似于打扑克时抓起一把乱牌理顺的过程，代码如下：
 
public class 插入 {
    public static void main(String[] args) {
        int[] arr={8,4,2,3,6};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void insertSort(int[] arr) {
        //分析，首先需要确定待插入的数
        //先做第一轮，待插入的数下标为1，定义插入的位置
        int insert = 0;
        int insertDex = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            insert = arr[i + 1];
            insertDex = i;
            while (insertDex >= 0 && insert < arr[insertDex]) {
                arr[insertDex + 1] = arr[insertDex];
                insertDex--;
            }
            //当循环退出时，插入的位置应该在insertDex+1的位置
            arr[insertDex + 1] = insert;
        }
    }
}
 
5、希尔排序 
希尔排序是把记录按下标的方式进行分组，对每一组使用直接插入排序算法排序，流程图如下：
 
 
1、交换法 
public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr={8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void shellSort(int[] arr) {
        int temp = 0;
        int gap = arr.length / 2;
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            gap = gap / 2;
        }
    }
}
 
交换法存在问题，类似是冒泡的从右到左，效率并不高
 
2、移位法 
移位法是在分组后直接用插入排序的方式对每一组进行排序。
移位法排序的功能代码如下：
 
 public static void shellSort1(int[] arr){
        for (int gap =arr.length/2 ; gap>0 ; gap/=2) {
            for (int i = gap; i =0&&temp

JAVA排序算法笔记

Java相关栏目本月热门文章