冒泡排序

思路：在一个数组中，将当前的索引的值与后一个做比较如果更大就交换，直到交换到最后一位。

详细实现：

第一个for循环控制总体遍历的次数。

为什么是判断条件是n - 1呢？因为只剩一个数的时候就不需要进行排序了。

第二个for循环是为了交换元素，比较大小，大的向后移动。

为什么要引入swaped变量呢？是一种优化思路，如果是个有序数组，就不用交换了。节约资源消耗。

public class Solution {public void bubbleSort(int[] arr, int n) {for (int i = 0; i < n - 1; i++) {boolean swaped = false;for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;swaped = true;                    }}if (!swaped) break;}}
}

插入排序

思路：模拟了整理扑克牌，分为两部分，左边是排好序的，右边是未排序的。遍历右边插入左边。

详细实现：第一个元素视为排好序的，for循环遍历右边数组。如果当前元素比已经排序好的元素大，正常插入到后面。如果小，移动已经排序好的元素，插入到正确位置。

public class Solution {public void insertSort(int[] arr, int n) {//从第二个元素开始，第一个元素视为已排序for (int i = 1; i < n; i++) {int j = i - 1;int value = arr[i];//当前要插入的元素while (j >= 0 && arr[j] > value) {arr[j + 1] = arr[j];元素右移j--;}arr[j + 1] = value;//插入正确位置}}
}

选择排序

思路：先选择一个数当最小值，遍历整个数组寻找最小值，如果比当前值小就交换。

详细实现：

外层for循环依然表示排序次数，因为一次可以确定一个最小值。

minIndex是最小值索引。

最后就是遍历和交换的步骤。

public class Solution {public void selectSort(int[] arr, int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}if (minIndex != i) {int tmp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = tmp;}}}
}

快速排序

思路：找一个基准数（通常用最后一个数），比他小的放到基数前，大的放在后面。

详细实现：递归实现排序，low<high表示还有元素需要排序。

把最后一个元素当作基数，循环遍历数组，如果找到比基数小的，交换当前元素和小于基数的索引位置。最后把基数放到正确的位置，即比基数小的索引加一。

public class Solution {public void quickSort(int[] arr, int n) {quickSortMethod(arr, 0, n - 1);}private void quickSortMethod(int[] arr, int low, int high) {if (low < high) {int pivotIndex =  partition(arr, low, high);quickSortMethod(arr, low, pivotIndex - 1);quickSortMethod(arr, pivotIndex + 1, high);}}private int  partition(int[] arr, int low, int high) {int i = low - 1;int pivot = arr[high];for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int tmp1 = arr[j];arr[j] = arr[i];arr[i] = tmp1;}}int tmp2 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = tmp2;return i + 1;}
}

归并排序

思路：将数组一分为二，先排序两侧，在合并的时候排序整体

详细设计：

先计算中间的索引。进行递归，先分为左数组和右数组，将原数组中的数拷贝到左右数组中。

合并操作是判断左右两个数组中哪个元素更小，放到原数组中。

最后剩余元素拷贝回原数组。

public class Solution {public void mergeSort(int[] arr, int n) {if (n < 2) return;mergeSortMethod(arr, 0, n - 1);}private void mergeSortMethod(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSortMethod(arr, left, mid);mergeSortMethod(arr, mid + 1, right);merge(arr, left, mid, right);}}private void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int[] leftArr = new int[n1];int[] rightArr = new int[n2];for (int i = 0; i < n1; i++) {leftArr[i] = arr[left + i];}for (int i = 0; i < n2; i++) {rightArr[i] = arr[mid + 1 + i];}int i = 0;int j = 0;int k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}while (i < n1) {arr[k++] = leftArr[i++];}while (j < n2) {arr[k++] = rightArr[j++];}}
}