数组
- 如何插入一条新的数据项
- 如何寻找某一特定的数据项
- 如何删除某一特定的数据项
- 如何迭代的访问各个数据项，以便进行显示或其他操作
无序数组
public class HighArray {
private Long[] arr;
private int item;
public HighArray(int length) {
arr = new Long[length];
item = 0;
}
public int find(long param) {
for (int i = 0; i < item; i++) {
if (arr[i] == param) {
return i;
}
}
return -1;
}
public boolean delete(long param) {
int j = find(param);
if (j == -1) {
return false;
}
for (int i = j; i < item - 1; i++) {
arr[i] = arr[i + 1];
}
item--;
return true;
}
public void insert(long param) {
arr[item] = param;
item++;
}
public void dispaly() {
System.out.print("[");
for (int i = 0; i < item; i++) {
System.out.print(arr[i]);
if (i != item - 1) {
System.out.print(",");
}
}
System.out.println("]");
}
}
有序数组
有序数组的查找速度比无序数组快得多,不好的方面是在插入操作中由于所有靠后的数据都需要移动以腾开控件,所以速度较慢
public class OrderArray {
private Long[] arr;
private int item;
public int find(long param) {
int begin = 0;
int end = item - 1;
int z;
while (true) {
z = (begin + end) / 2;
System.out.print(begin + " ");
System.out.print(end + " ");
System.out.println(z);
if (begin > end) {
return -1;
}
if (arr[z] > param) {
end = z - 1;
} else if (arr[z] < param) {
begin = z + 1;
} else {
return z;
}
}
}
public void insert(long param) {
int j;
for (j = 0; j < item; j++) {
if (param < arr[j]) {
break;
}
}
for (int i = item; i > j; i--) {
arr[i] = arr[i - 1];
}
arr[j] = param;
item++;
}
}
线性查找
二分查找
①、插入快，对于无序数组，上面我们实现的数组就是无序的，即元素没有按照从大到小或者某个特定的顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但是有序数组却不一定了，它需要在指定的位置插入。
②、查找慢，当然如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，我们需要从数组第一个元素开始遍历，直到找到那个元素。有序数组通过特定的算法查找的速度会比无需数组快。
③、删除慢，根据元素值删除，我们要先找到该元素所处的位置，然后将元素后面的值整体向前面移动一个位置。也需要比较多的时间。
④、数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。
排序算法
冒泡排序
冒泡算法的运作规律如下：
①、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（也就是第一波冒泡完成）。
③、针对所有的元素重复以上的步骤，除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
public void sort() {
for (int i = item; i > 0; i--) {
for (int j = 1; j < i; j++) {
if (arr[j] < arr[j - 1]) {
swap(j, j - 1);
}
}
dispaly();
}
}
private void swap(int in, int out) {
long temp = arr[in];
arr[in] = arr[out];
arr[out] = temp;
}
[2,7,5,8,9,1,4,6,3,0]
第0轮 [2,5,7,8,1,4,6,3,0,9]
第1轮 [2,5,7,1,4,6,3,0,8,9]
第2轮 [2,5,1,4,6,3,0,7,8,9]
第3轮 [2,1,4,5,3,0,6,7,8,9]
第4轮 [1,2,4,3,0,5,6,7,8,9]
第5轮 [1,2,3,0,4,5,6,7,8,9]
第6轮 [1,2,0,3,4,5,6,7,8,9]
第7轮 [1,0,2,3,4,5,6,7,8,9]
第8轮 [0,1,2,3,4,5,6,7,8,9]
第9轮 [0,1,2,3,4,5,6,7,8,9]
冒泡排序性能分析：
假设参与比较的数组元素个数为 N，则第一轮排序有 N-1 次比较，第二轮有 N-2 次，如此类推，这种序列的求和公式为：
（N-1）+（N-2）+...+1 = N*（N-1）/2
交换和比较次数都和N2 成正比。由于常数不算大 O 表示法中，忽略 2 和 4，那么冒泡排序运行都需要 O(N2) 时间级别。
选择排序
选择排序是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
分为三步：
①、从待排序序列中，找到关键字最小的元素
②、如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换
③、从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束
public void sort() {
for (int i = 0; i < item; i++) {
int min = i;
for (int j = i + 1; j < item; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(i, min);
dispaly();
}
}
[2,7,5,8,9,1,4,6,3,0]
第0轮 [0,7,5,8,9,1,4,6,3,2]
第1轮 [0,1,5,8,9,7,4,6,3,2]
第2轮 [0,1,2,8,9,7,4,6,3,5]
第3轮 [0,1,2,3,9,7,4,6,8,5]
第4轮 [0,1,2,3,4,7,9,6,8,5]
第5轮 [0,1,2,3,4,5,9,6,8,7]
第6轮 [0,1,2,3,4,5,6,9,8,7]
第7轮 [0,1,2,3,4,5,6,7,8,9]
第8轮 [0,1,2,3,4,5,6,7,8,9]
第9轮 [0,1,2,3,4,5,6,7,8,9]
选择排序性能分析：
选择排序和冒泡排序执行了相同次数的比较：N*（N-1）/2，但是至多只进行了N次交换。
当 N 值很大时，比较次数是主要的，所以和冒泡排序一样，用大O表示是O(N2) 时间级别。但是由于选择排序交换的次数少，所以选择排序无疑是比冒泡排序快的。当 N 值较小时，如果交换时间比选择时间大的多，那么选择排序是相当快的。
插入排序
直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止
public void sort() {
//从下标1开始循环
for (int i = 1; i < item; i++) {
long temp = arr[i];//记录要插入的值
int j = i;
while (j > 0 && arr[j - 1] >= temp) {//找到比要插入的值要大的数
arr[j] = arr[j - 1];//大数向后移动
j--;
}
arr[j] = temp;//插入数据
dispaly();
}
}
[2,7,5,8,9,1,4,6,3,0]
第1轮 [2,7,5,8,9,1,4,6,3,0]
第2轮 [2,5,7,8,9,1,4,6,3,0]
第3轮 [2,5,7,8,9,1,4,6,3,0]
第4轮 [2,5,7,8,9,1,4,6,3,0]
第5轮 [1,2,5,7,8,9,4,6,3,0]
第6轮 [1,2,4,5,7,8,9,6,3,0]
第7轮 [1,2,4,5,6,7,8,9,3,0]
第8轮 [1,2,3,4,5,6,7,8,9,0]
第9轮 [0,1,2,3,4,5,6,7,8,9]
插入排序性能分析：
在第一轮排序中，它最多比较一次，第二轮最多比较两次，一次类推，第N轮，最多比较N-1次。因此有 1+2+3+...+N-1 = N*（N-1）/2。
假设在每一轮排序发现插入点时，平均只有全体数据项的一半真的进行了比较，我们除以2得到：N*（N-1）/4。用大O表示法大致需要需要 O(N2) 时间级别。
复制的次数大致等于比较的次数，但是一次复制与一次交换的时间耗时不同，所以相对于随机数据，插入排序比冒泡快一倍，比选择排序略快。
这里需要注意的是，如果要进行逆序排列，那么每次比较和移动都会进行，这时候并不会比冒泡排序快。
快速排序
快速排序的基本思路
一、先通过第一趟排序，将数组原地划分为两部分，其中一部分的所有数据都小于另一部分的所有数据。原数组被划分为2份
二、通过递归的处理， 再对原数组分割的两部分分别划分为两部分，同样是使得其中一部分的所有数据都小于另一部分的所有数据。 这个时候原数组被划分为了4份
三、就1,2被划分后的最小单元子数组来看，它们仍然是无序的，但是！ 它们所组成的原数组却逐渐向有序的方向前进。
四、这样不断划分到最后，数组就被划分为多个由一个元素或多个相同元素组成的单元，这样数组就有序了。
private void quickSort(int start, int end) {
long temp = arr[start];
int i = start;
int j = end;
System.out.println("start:" + start + " end:" + end);
while (i < j) {
while (i < j && arr[j] > temp) {
j--;
}
while (i < j && arr[i] < temp) {
i++;
}
if (i < j && arr[i] == arr[j]) {
i++;
} else {
swap(i, j);
}
}
dispaly();
if (i - 1 > start) {
quickSort(start, i - 1);
}
if (j + 1 < end) {
quickSort(j + 1, end);
}
}
[2,7,5,8,9,1,4,6,3,0]
start:0 end:9
[0,1,2,8,9,5,4,6,3,7]
start:0 end:1
[0,1,2,8,9,5,4,6,3,7]
start:3 end:9
[0,1,2,7,3,5,4,6,8,9]
start:3 end:7
[0,1,2,6,3,5,4,7,8,9]
start:3 end:6
[0,1,2,4,3,5,6,7,8,9]
start:3 end:5
[0,1,2,3,4,5,6,7,8,9]
希尔排序
希尔排序应运而生了，希尔排序通过加大插入排序中元素的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度的移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，最后间隔为1时，就是我们上面说的简单的直接插入排序。
public void sort() {
int gap = item;
while (true) {
gap /= 2.2; //增量每次减半
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < item; j += gap) {//这个循环里其实就是一个插入排序
long temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp) {
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
System.out.println("增量为 "+gap);
dispaly();
if (gap == 1)
break;
}
}
[2,7,5,8,9,1,4,6,3,0]
增量为 4
[2,0,4,6,3,1,5,8,9,7]
增量为 1
[0,1,2,3,4,5,6,7,8,9]
地精排序
号称最简单的排序算法,只有一层循环,默认情况下前进冒泡,一旦遇到冒泡的情况发生就往回冒,直到把这个数字放好为止
public void sort() {
int j = 1;
while (j < item) {
if (j == 0 || arr[j] > arr[j - 1]) {
j++;
} else {
swap(j, j - 1);
j--;
}
}
}
