排序算法

排序算法介绍

排序也称为排序算法，排序是将一组数据，依照指定的顺序进行排序的过程。

排序的分类

（1）内部排序：

指将需要处理的所有数据都加载到内部存储器（内存）中进行排序

（2）外部排序法：

数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序

（3）常见的内部排序算法分类：

内部排序主要分为：插入排序、选择排序、交换排序、归并排序、基数排序

算法的时间复杂度

时间频度

时间频度是一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费的时间就多。

一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）

时间复杂度

（1）一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T（n）表示，若有某个辅助函数

f（n），使得当n趋近于无穷大时，T（n）/f（n）的极限值为不等于零的常数，则称f（n）是T（n）的同数量级函

数。记作T（n）=O（f（n）），称O（f（n））为算法的渐进时间复杂度，简称时间复杂度。

（2）T（n）不同，但时间复杂度可能相同。

（3）计算时间复杂度的方法：

1）用常数1代替运行时间中的所有加法常数

2）修改后的运行次数函数中，只保留最高阶项

3）去除最高阶项的系数

（4）常见的时间复杂度

1）常数阶O（1）

2）对数阶O（log2n）

3）线性阶O（n）

4）线性对数阶O（nlog2n）

5）平方阶O（n^2）

6）立方阶O（n^3）

7）k次方阶O（n^k）

8）指数阶O（2^n）

使用冒泡法进行数据排序

介绍

冒泡排序的基本思想是通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则

进行交换，使值较大的元素逐渐从前向后移。

优化

因为排序的过程中，各元素不断j接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序

过程中设置一个表示flag判断元素是否进行过交换。从而减少不必要的比较。

// 将五个无序的数：24，69，80，57，13 
// 使用冒泡排序法将其排成一个 从小到大 的有序数列
 
public class BubbleSort {
	public static void main(String[] args) {
        int[] arr = {24 , 69 , 80 , 57 , 13};
		int temp; //用于辅助变量交换
 
		// 4就是 arr.length - 1
		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 + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
				}
			}
        // 每一轮循环可以确定一个数的位置，比如第一轮排序确定最大的数，第二轮排序
        //确定第二大的数，以此类推
 
			System.out.println("\n ===第" + (i + 1) + "轮");
			for(int j = 0; j < arr.length ; j++) {
				System.out.print(arr[j] + "\t");
				}
			}
		}
	}