初始化数组：
static int array[] = new int[5];
array[0] = 12;
array[1] = 3;
array[2] = 1;
array[3] = 8;
array[4] = 10;
冒泡排序
原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。 - 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
// 冒泡排序，思路是把最大的值，朝最后面移动，一轮循环下来，可以选一个最大的值到最后
// 时间复杂度为O(n平方)
public static void bubble() {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
int temp = 0;
if (array[j] > array[j + 1]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
如果数字已经有序，可以优化，优化后的代码如下：
// 优化的冒泡，一轮下来，没有任何移动，就停止，认为已经是有序的
public static void bubble1() {
int index = 0;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
int temp = 0;
if (array[j] > array[j + 1]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
index++;
}
}
if (index == 0)
break;
}
}
选择排序
- 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置
- 然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾
- 以此类推，直到全部待排序的数据元素的个数为零
// 选择排序，每次选择一个最小的，放在最前面
public static void selectSort() {
for (int i = 0; i < array.length; i++) {
int min = array[i];
int index = i;
for (int j = i; j < array.length; j++) {
if (array[j] < min) {
min = array[j];
index = j;
}
}
int temp = array[i];
array[i] = min;
array[index] = temp;
}
}
快速排序
它采用了一种分治的策略，通常称其为分治法
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用
基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
以下为代码示例和说明：
1．i =L; j = R; 将基准数挖出形成第一个坑s[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑s[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑s[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入s[i]中。
static void quickSort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
插入排序
插入排序法思想：
- 把 n 个待排序的元素看成为一个有序表和一个无序表，开始时 有
序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排
序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
将n个元素的数列分为已有序和无序两个部分。 - 更形象点的数据示例
数列：{a1，a2，a3，a4，…，an}
将该数列的第一元素视为有序数列，后面都视为无序数列：
{{a1}，{a2，a3，a4，…，an}}
将无序数列中的元素插入到有序数列的对应位置，插入前通过比大小的方式找到其在有序数列中的对应位置。 -
插入过程动画图如下：
insertionSort.gif - 代码示例：
static void insertSort(int arr[]){
for (int i = 1; i < arr.length; i++) {
// 记录要插入的数据
int tmp = arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// 存在比其小的数，插入
if (j != i) {
arr[j] = tmp;
}
}
}
希尔排序
希尔排序也是一种 插入排序，它是简单插入排序经过改进之后的一个 更高效的版本，也称为 缩小增量排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含
的关键词越来越多， 当增量减至 1 时，整个文件恰被分成一组，算法便终止
如图：
112.png
代码表示分别有移动法和交互法：
- 移动法：
/**
* 希尔排序 针对有序序列在插入时采用移动法。
*/
public static void sort1(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;
}
arr[j] = temp;
}
}
}
}
- 交换法:
/**
* 交换数组元素
*
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b) {
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 希尔排序 针对有序序列在插入时采用交换法
*
* @param arr
*/
public static void sort(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;
while (j - gap >= 0 && arr[j] < arr[j - gap]) {
// 插入排序采用交换法
swap(arr, j, j - gap);
j -= gap;
}
}
}
}
归并排序
- 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的 分治 （divide-and-conquer ）
策略（分治法将问题分(divide)成一些 小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修
补"在一起，即分而治之)
115.png
114.png
- 代码示例：
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
