数组排序

简介:重点掌握冒泡,选择,快速排序

冒泡排序

相邻的俩个进行俩俩比较.

每一轮比较完 - 确定一个最值

9 3 1 7 5 2 1

3 9 1 7 5 2 1

3 1 9 7 5 2 1

3 1 7 9 5 2 1

3 1 7 5 9 2 1

3 1 7 5 2 9 1

3 1 7 5 2 1 9

选择排序

9 3 1 7 5 2 6

arr[0] -> 依次和 后面所有的元素进行比较

3 9 1 7 5 2 6

1 9 3 7 5 2 6

确定最值

arr[1] -> 依次和后面的所有的元素进行比较

1 2 9 7 5 3 6

直接插入排序

简介:最简单的

将数组中剩余的值(从数组中第2个位置开始)依次直接插入到前面,保证前面的序列仍然是一个有序的序列

{3,1,2,5,4,6}

{3,1,2,5,4,6}

{1,3,2,5,4,6}

{1,2,3,5,4,6}

…

快速排序

算法思想:

分治思想:比大小,再分区

1. 从数组中取出一个数,作为基准数
2. 分区:将比这个数[基准数]大或者等于的数全部放在它的右边,小于它的数全部放在它的左边
3. 再对左右分区间重复第二步骤,直到各分区只有一个数

实现思路:

挖坑填数

1. 将基准数挖出形成第一个坑
2. 由后向前找比它小的数,找到后挖出此数填到前一个坑中
3. 由前向后找比它大或等于的数,找到后也挖出此数填到前一个坑中
4. 再重复执行2,3两步骤.例如对5391672408

元素	5	3	9	1	6	7	2	4	0	8
坑位	坑1		坑3		坑5	坑7	坑6	坑4	坑2
	0	3	4	1	2	基准数5	7	6	9	8
坑位						pos

元素	5[基准数]	3	9	1	6	7	2	4	0	8
坑位	坑1		坑3		坑5	坑7	坑6	坑4	坑2
	0	3	4	1	2	基准数5	7	6	9	8
坑位						第一次重合的位置

第一轮以数组中的第一个元素5为基准数 - 经过一轮循环走完 - 以5位置为基准,左边的都是比5小的值,右边的都是大于或者等于5的数字 - 关键就是找到重合的位置!!!(分区 - 递归调用)

int[] arr = {5,3,9,1,6,7,2,4,0,8};

其他排序

• 希尔排序
• 堆排序
• 归并排序