JAVA入门学习笔记----数组排序

一、什么是数组

　　* 数组是一个变量，存储相同数据类型的一组数据；

　　* 声明一个变量就是在内存空间划出一块合适的空间

　　* 声明一个数组就是在内存空间划出一串连续的空间

　　二、数组的基本要素

　　标识符：数组的名称，用于区分不同的数组

　　数组元素：向数组中存放的数据

　　元素下标：对数组元素进行编号从0开始，数组中的每个元素都可以通过下标来访问

　　元素类型：数组元素的数据类型

　　注意：

　　* 数组长度固定不变，避免数组越界。

　　* 数组中的所有元素必须属于相同的数据类型。

　　三、如何使用数组

　　使用数组4步走：

　　1.声明数组 int[] a;

　　2.分配空间 a = new int[5];

　　3. 赋值 a[0] = 8;

　　4.处理数据 a[0] = a[0] * 10;

　　四、数组排序

　　1. Arrays.sort(数组名); 升序排列（从小到大）

　　2.冒泡排序

　　原理：比较两个相邻的元素，将值大的元素交换到右边；

　　思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

　　(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

　　(2)比较第2和第3个数，将小数放在前面，大数放在后面。

　　......

　　(3)如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

　　(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

　　(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

　　(6)依次类推，每一趟比较次数减少依次

　　3.选择排序

　　原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。

　　1：从a[0]-a[N-1]中选出最小的数据，然后与a[0]交换位置

　　2：从a[1]-a[N-1]中选出最小的数据，然后与a[1]交换位置（第1步结束后a[0]就是N个数的最小值）

　　3：从a[2]-a[N-1]中选出最小的数据，然后与a[2]交换位置（第2步结束后a[1]就是N-1个数的最小值

　　4.桶排序

　　原理：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并

　　计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

　　1.找出待排序数组中的最大值max、最小值min

　　2.我们使用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1

　　3.遍历数组 arr，计算每个元素 arr[i] 放的桶

　　4.每个桶各自排序

　　5.遍历桶数组，把排序好的元素放进输出数组

　　5.希尔排序

　　原理：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

　　我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

　　6.快速排序

　　原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。