数据结构与算法二之排序算法_数据结构什么时候数量级是olog2n

时间复杂度

引出：时间频度：
一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。
T(n)的求解：1、忽略常数项。 2、忽略低次项 。3、忽略系数。
例如：T(n) = 3n^2+3n+6 ——>n^2

时间复杂度：
f(n)：即三忽略后的辅助函数。
T(n) / f(n) 的极限值为不等于零的常数，则称 f(n)是 T(n)的同数量级函数。
记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

常见的时间复杂度：

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)

以上由从小到大排列，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

1、对数阶 O(log2n)

int i = 1;
while(i<n){
	i = i *2;
}
//说明：假设循环 x 次跳出，则2^x = n ,所以x = log2n
1
2
3
4
5

2、线性阶 O(n)

for (int i = 0; i < n; i++) {
      j++;
 }
//说明：for 循环中的代码执行 n 遍。
1
2
3
4

3、线性对数阶 O(nlog2n)
上述两者互相包含

4、平方阶 O(n^2)
两个O(n) 互相包含

常见排序算法（八种）

时间复杂度比较：

冒泡排序

基本思想：（数组）
待排序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，就像水底下的气泡一样逐渐向上冒。

优化：
如果一趟比较下来没有进行过交换，就说明序列已经有序，因此要在 排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。

代码实现：

	public static void bubbleSort(int[] arr) {
		// 冒泡排序 的时间复杂度 O(n^2)

		int temp = 0; 		// 临时变量
		boolean flag = false; 			// 标识变量，表示是否进行过交换
		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]) {
					flag = true;
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
			if (!flag) { 	// 在一趟排序中，一次交换都没有发生过
				break;
			} else {
				flag = false; 	// 重置flag!!!, 进行下次判断
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

选择排序

与冒泡排序类似，冒泡一趟排序确认后面的一位数的位置；选择排序则确认前面一位的位置。（第一趟确认第一位数，第二趟确认第二位…）

不同的是：
冒泡每次比较相邻的两位，逆序则交换位置；
选择先假定一个数为最值，记录它的位置和值，在一趟排序中，逐一与剩下的数比较，最终确认此趟中的最值 位置和值，将它与此趟首位交换。从而确定一个位置；

代码实现：

	public static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;	//记录下标
			int min = arr[i];	//记录值
			for (int j = i + 1; j < arr.length; j++) {
				if (min > arr[j]) { 	// 说明假定的最小值，并不是最小
					min = arr[j]; 	// 重置min
					minIndex = j; 	// 重置minIndex
				}
			}
			if (minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插入排序

基本思想：

把 n 个待排序的元素看成为一个有序表和一个无序表，
开始时 有序表中只包含一个元素，无序表中包含有 n-1 个元素，
排序过程中每次从无序表中取出第一个元素，，将它插入到有序表中的适当位置

图解：

代码实现：
与选择排序一样，将待排序的数字保存在一个临时变量，避免比较过程丢失。

	public static void insertSort(int[] arr) {
		int insertVal = 0;
		int insertIndex = 0;
		for(int i = 1; i < arr.length; i++) {
			
			insertVal = arr[i];	 //定义待插入的数
			insertIndex = i - 1;  //定义首个要比较数的下标

			// 给insertVal 找到插入的位置
			// 说明
			// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
			// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
			// 3. 就需要将 arr[insertIndex] 后移
			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex];	//后移
				insertIndex--;	//找前一个数继续比较
			}
			
			// 当退出while循环时，说明插入的位置找到, insertIndex + 1
			//这里我们判断是否需要赋值
			if(insertIndex + 1 != i) {	
				arr[insertIndex + 1] = insertVal;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

希尔排序

引出：简单插入排序的缺陷：
当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响（假定从小到大）

希尔排序：它也是一种插入排序，是简单插入的改良版本，也称缩小增量排序。

基本思想：

把数字按下标的一定步长分组，对每组使用直接插入排序算法排序；
随着步长逐渐减少，每组的数字越来越多，
当步长减至 1 时，整个文件恰被分成一组，算法便终止

	public static void shellSort(int[] arr) {
		
		// 增量gap, 并逐步的缩小增量
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {	//一次循环代表一趟
			// 从第gap个元素开始（其前面是有序列），逐个直接插入排序，插入前面的有序列中
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];	//记录待插入的数值，原理与直接插入相同。
				if (arr[j] < arr[j - gap]) {	//判断！是否已经在正确的位置上了
					while (j - gap >= 0 && temp < arr[j - gap]) {
						arr[j] = arr[j-gap];	//前一个数后移
						j -= gap;				//往前继续比较
					}
					//当退出while后，就给temp找到插入的位置
					arr[j] = temp;
				}
			}
		}
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序

快速排序是冒泡排序的改良版本。（和冒泡排序一样通过交换来调整位置）

基本思路：

1. 选取基准点（以中间轴为例）
2. 分别从左往右找 <= 基准点的数；从右往左找 >= 基准点的数
3. 每找到一个将他们交换位置；
4. 当他们遍历完所有数时（同时指向同一个数），完成一次排序
5. 可以看到基准点前面都是小于等于它的数，后面都是大于等于它的数
6. 再对两边序列重复上述过程（使用递归）即可

public static void quickSort(int[] arr,int left, int right) {
		int l = left; 	//最左下标
		int r = right; 	//最右下标
		//pivot 中轴值（选取中间数为基准点）
		int pivot = arr[(left + right) / 2];
		int temp = 0; //临时变量，作为交换时使用
		
		//while循环的目的是让比pivot 值小放到左边；比pivot 值大放到右边
		while( l < r) { 
			//在pivot的左边一直找,找到大于等于pivot值,才退出
			while(arr[l] < pivot) {
				l += 1;
			}
			//在pivot的右边一直找,找到小于等于pivot值,才退出
			while(arr[r] > pivot) {
				r -= 1;
			}
			//完成一次遍历
			if( l == r) {
				break;
			}
			
			//交换
			temp = arr[l];
			arr[l] = arr[r];
			arr[r] = temp;
			
			//下面两种时特殊情况处理：当遇到两个以上基准点值
			//如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
			if(arr[l] == pivot) {	
				r -= 1;
			}
			//如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
			if(arr[r] == pivot) {
				l += 1;
			}
		}
		
		// 如果 l == r, 必须l++, r--, 否则为出现栈溢出
		if (l == r) {	//基准点不再参与排序
			l += 1;
			r -= 1;
		}
		//向左递归
		if(left < r) {
			quickSort(arr, left, r);
		}
		//向右递归
		if(right > l) {
			quickSort(arr, l, right);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

归并排序

该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

基本思想：

1. 通过两个递归将一个序列，向左向右逐步分解成一个个独立的元素
2. 将一个个子序列逐步向上归并（排序）

相邻两个子序列合并过程：需要一个辅助数组

代码实现：

	//分+合方法
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if(left < right) {
			int mid = (left + right) / 2; //中间索引
			//向左递归进行分解
			mergeSort(arr, left, mid, temp);
			//向右递归进行分解
			mergeSort(arr, mid + 1, right, temp);
			//合并
			merge(arr, left, mid, right, temp);
		}
	}

	/**	合并的方法
	 * @param arr 排序的原始数组
	 * @param left 左边有序序列的初始索引
	 * @param mid 中间索引
	 * @param right 右边索引
	 * @param temp 做中转的数组
	 */
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {

		int i = left; // 初始化i, 左边有序序列的初始索引
		int j = mid + 1; //初始化j, 右边有序序列的初始索引
		int t = 0; // 指向temp数组的当前索引

		//(一)
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列，有一边处理完毕为止
		while (i <= mid && j <= right) {
			//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
			//即将左边的当前元素，填充到 temp数组
			//然后 t++, i++
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else { //反之,将右边有序序列的当前元素，填充到temp数组
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}

		//(二)
		//把有剩余数据的一边的数据依次全部填充到temp
		while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[i];
			t += 1;
			i += 1;
		}

		while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}

		//(三)
		//将temp数组的元素拷贝到arr
		//注意，并不是每次都拷贝temp的所有数据，只拷贝两个子序列排序后的元素
		t = 0;
		int tempLeft = left; 
		//第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
		//最后一次 tempLeft = 0  right = 7
		while(tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

基数排序

概述
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

实现图解：
待排序列：

第一次按个位排序：每次排序完，都按从左往右，从上到下的顺序取出。

第二次按十位排序：

第三次按百位排序：如果有四位数当然也要第四次按千位啦

代码实现：

public static void radixSort(int[] arr) {

        int max = Integer.MIN_VALUE;	//用于记录待排序列中最大的数
        for (int i = 0; i < arr.length; i++) {	//循环结束即可得到最大数
            if (max < arr[i]) {
                max = arr[i];
            }
        }

        int[][] temp = new int[10][arr.length];	//利用二维数组模拟0-9 十个桶
        int counts[] = new int[10];		//记录放完之后每个桶中的元素个数
        int maxLength = (max + "").length();	//最大数是几位数，就要循环排序几遍
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {	//个十百千。。循环
            for (int j = 0; j < arr.length; j++) {	
            //遍历一次待排序列，计算每个数对应位的数字（余数），按数放入桶中
                int ys = arr[j] / n % 10;
                temp[ys][counts[ys]] = arr[j];
                counts[ys]++;
            }

            int index = 0;
            for (int k = 0; k < counts.length; k++) {
            //循环将放入桶中的元素依次取出，得到一个新的序列
                if (counts[k] != 0) {	//桶中有元素才取
                    for (int l = 0; l < counts[k]; l++) {
                        arr[index] = temp[k][l];
                        index++;
                    }
                    counts[k] = 0;	//这步容易忽略！！！
                    //将一个桶中的所有元素取出后，需要将其标记置为0，方便下次排序；
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34