排序算法
排序算法中包括：简单排序、高级排序
简单排序
简单排序常用的有：冒泡排序、选择排序、插入排序
- 冒泡排序代码如下：
private static void bubbleSrot(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
冒泡排序方法速度是很慢的，运行时间为O（N²）级。选择排序改进了冒泡排序，将必要的交换次数从O（N²）减少到O（N），不幸的是比较次数依然是O（N²）级。然而，选择排序依然为大记录量的排序提出了一个非常重要的改进，因为这些大量的记录需要在内存中移动，这就使交换的时间和比较的时间相比起来，交换的时间更为重要。
---------------------
- 选择排序代码如下：
private static void chooseSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int least = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[least]) {
least = j;
}
}
// 将当前第一个元素与它后面序列中的最小的一个 元素交换，也就是将最小的元素放在最前端
int temp = arr[i];
arr[i] = arr[least];
arr[least] = temp;
}
}
选择排序的效率：选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2。对于10个数据项，需要45次比较，然而，10个数据项只需要少于10次的交换。对于100个数据项，需要4950次比较，但只进行不到100次交换。N值很大时，比较的次数是主要的，所以结论是选择排序和冒泡哦排序一样运行了O（N²）时间。但是，选择排序无疑更快，因为它进行的交换少得多。
---------------------
- 插入排序代码如下：
private static void insertionSort(int[] arr) {
int in, out;
for (out = 1; out < arr.length; out++) {
int temp = arr[out];
in = out;
while (in > 0 && arr[in - 1] >= temp) {
arr[in] = arr[in - 1];
--in;
}
arr[in] = temp;
}
}
插入排序的效率：这个算法中，第一趟排序，最多比较一次，第二趟排序，最多比较两次，以此类推，最后一趟最多比较N-1次，因此有1+2+3+…+N-1 = N*(N-1)/2。然而，因为在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，所以除以2最后是N*(N-1)/4。
对于随机顺序的数据，插入排序也需要O（N²）的时间级。当数据基本有序，插入排序几乎只需要O(N)的时间，这对把一个基本有序的文件进行排序是一个简单而有效的方法。
对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。
---------------------
归并排序
// 将两个已排序的数组合并到第三个数组上。
private static void merge(int[] arrA, int[] arrB, int[] arrC) {
int aDex = 0, bDex = 0, cDex = 0;
int sizeA = arrA.length;
int sizeB = arrB.length;
// A数组和B数组都不为空
while (aDex < sizeA && bDex < sizeB) {
if (arrA[aDex] < arrB[bDex]) {
arrC[cDex++] = arrA[aDex++];
} else {
arrC[cDex++] = arrB[bDex++];
}
}
// A数组不为空，B数组为空
while (aDex < sizeA) {
arrC[cDex++] = arrA[aDex++];
}
// A数组为空，B数组不为空
while (bDex < sizeB) {
arrC[cDex++] = arrB[bDex++];
}
}
高级排序
常见的高级排序：哈希排序、快速排序，这两种排序算法都比简单排序算法快得多：希尔排序大约需要O(N*(logN)²)时间，快速排序需要O(N*logN)时间。这两种排序算法都和归并排序不同，不需要大量的辅助存储空间。希尔排序几乎和归并排序一样容易实现，而快速排序是所有通用排序算法中最快的一种排序算法。 还有一种基数排序，是一种不常用但很有趣的排序算法。
- 哈希排序
哈希排序是基于插入排序的，实现代码如下：
private static void shellSort(int[] arr) {
int inner, outer;
int temp;
int h = 1;
int nElem = arr.length;
while (h <= nElem / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (outer = h; outer < nElem; outer++) {
temp = arr[outer];
inner = outer;
while (inner > h - 1 && arr[inner - h] >= temp) {
arr[inner] = arr[inner - h];
inner -= h;
}
arr[inner] = temp;
}
h = (h - 1) / 3;
}
}
---------------------
- 快速排序
快速排序是最流行的排序算法，在大多数情况下，快速排序都是最快的，执行时间是O(N*logN)级，划分是快速排序的根本机制。划分本身也是一个有用的操作。 划分数据就是把数据分为两组，使所有关键字大于特定值的数据项在一组，所有关键字小于特定值的数据项在另一组。代码实现如下：
// 快速排序
private static void recQuickSort(int arr[], int left, int right) {
if (right - left <= 0) {
return;
} else {
int pivot = arr[right];// 一般使用数组最右边的元素作为枢纽
int partition = partitionIt(arr, left, right, pivot);
recQuickSort(arr, left, partition - 1);
recQuickSort(arr, partition + 1, right);
}
}
// 划分
private static int partitionIt(int[] arr, int left, int right, int pivot) {
int leftPtr = left - 1;
// int rightPtr = right + 1;
int rightPtr = right; // 使用最右边的元素作为枢纽，划分时就要将最右端的数据项排除在外
while (true) {
while (arr[++leftPtr] < pivot)
;
while (rightPtr > 0 && arr[--rightPtr] > pivot)
;
if (leftPtr >= rightPtr) {
break;
} else {
// 交换leftPtr和rightPtr位置的元素
int temp = arr[leftPtr];
arr[leftPtr] = arr[rightPtr];
arr[rightPtr] = temp;
}
}
// 交换leftPtr和right位置的元素
int temp = arr[leftPtr];
arr[leftPtr] = arr[right];
arr[right] = temp;
return leftPtr;// 返回枢纽位置
}
---------------------
查找算法
对于有序的数组，常用的查找算法：二分查找。代码如下：
private static int find(int [] arr,int searchKey){
int lowerBound = 0;
int upperBound = arr.length -1;
int curIn;
while(lowerBound <= upperBound){
curIn = (lowerBound + upperBound) / 2;
if(arr[curIn] == searchKey){
return curIn;
}else{
if(arr[curIn] < searchKey){
lowerBound = curIn + 1;
}else{
upperBound = curIn - 1;
}
}
}
return -1;
}
---------------------