一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序
//1.冒泡排序
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
二、快速排序
快速排序的基本思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。
//2、快速排序
/**
* @param arr 待排序列
* @param leftIndex 待排序列起始位置
* @param rightIndex 待排序列结束位置
*/
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
}
//从左开始的起点
int left = leftIndex;
//从右开始的起点
int right = rightIndex;
//默认左侧第一个元素为基准值
int key = arr[left];
//从两头开始交替扫描，知道left=right
while (left < right) {
//先从右边开始扫描
while (left < right && arr[right] >= key) {
right--;
}
//交换位置 把右边<key的值移到左边
arr[left] = arr[right];
//然后从左向右开始扫描
while (left < right && arr[left] <= key) {
left++;
}
//交换位置 把左边>key的值移到右边
arr[right] = arr[left];
}
//基准值归位
arr[left] = key;
//对基准值左侧的数组进行排序
quickSort(arr, leftIndex, left - 1);
//对基准值右侧的数组进行排序
quickSort(arr, right + 1, rightIndex);
}
三、选择排序
基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
//3 选择排序
public static void selectSort(int[] arr) {
int size = arr.length;
int temp;
int minIndex;
for (int i = 0; i < size - 1; i++) {
minIndex = i;//暂定第i个元素的位置
//找出i以后最小值，就是i位置上应该摆放的值。 其索引即是 minIndex
for (int j = i + 1; j < size; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
//交换两个元素
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
四、插入排序
1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
//4、插入排序
public static void insertSort(int[] arr) {
int size = arr.length;
int temp;
int j;
for (int i = 1; i < size; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
五、希尔排序
希尔排序的原理:根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值移到后面，最后将整个数组进行插入排序，这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强版的插入排序
- 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
- 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，4和比其下标值小increment的数组值相比较
- 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
- 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
*实现数组从大到小排
//5、希尔排序
public static void shellSort(int[] arr) {
int size = arr.length;
int j;
int temp;
for (int increment = size / 2; increment > 0; increment /= 2) {
for (int i = increment; i < size; i++) {
temp = arr[i];
for (j = i; j >= increment; j -= increment) {
if (temp < arr[j - increment]) {
arr[j] = arr[j - increment];
} else {
break;
}
}
arr[j] = temp;
}
}
}
六、归并排序
基本思想：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
//6、归并排序
public static int[] sort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
sort(arr, low, mid);
sort(arr, mid + 1, high);
merge(arr, low, high);
}
return arr;
}
public static void merge(int[] arr, int low, int high) {
int[] temp = new int[high - low + 1];
int mid = (low + high) / 2;
int i = low;//左数组 指针
int j = mid + 1;//右数组 指针
int k = 0;//数组temp的指针
while (i <= mid && j <= high) {//左右两个数组，至少有一个会先加完即i>mid或j>high，而退出循环
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
//①，②以下两个循环只会进入一个
//①把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = arr[i++];
}
//②把右边剩余的数移入数组
while (j <= high) {
temp[k++] = arr[j++];
}
//把临时数组覆盖到原数组
for (int i1 = 0; i1 < temp.length; i1++) {
arr[i1 + low] = temp[i1];
}
}
