选择排序
1.遍历整个序列，将最小的数放在最前面。
2.遍历剩下的序列，将最小的数放在最前面。
3.重复第二步，直到只剩下一个数。
/**
* 选择排序
* @param arr 待排序的数组
*/
public void selectSort(int[] arr){
for (int i=0;i<arr.length;++i){
for (int j=i+1;j< arr.length;++j){
if (arr[i]>arr[j]){
arr[i]^=arr[j];
arr[j]^=arr[i];
arr[i]^=arr[j];
}
}
}
}
基数排序（桶排序）
1.将所有的数的个位数取出，按照个位数进行排序，构成一个序列。
2.将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。
注意：负数不行，小数不行
public void radixSort(int[] arr) {
int maxArr = arr[0];
//首先获取数组中最大数的位数
for (int i = 0; i < arr.length; i++) {
if (maxArr < arr[i]) {
maxArr = arr[i];
}
}
//用特殊的方法获取整数的位数
int maxLength = (maxArr + "").length();
//准备开始排序
//首先创建10个桶，用来存放数据
int[][] bucket = new int[10][arr.length];
//每个水桶的索引(即 每个水桶 里面有多少个数据)
int[] bucketOfElement = new int[bucket.length];
for (int l = 0, n = 1; l < maxLength; l++, n *= 10) {
int currentnum = 0;
//将arr数组中的数 进行分开，分到对应的桶中
for (int i = 0; i < arr.length; i++) {
currentnum = arr[i] / n % 10;
bucket[currentnum][bucketOfElement[currentnum]] = arr[i];
bucketOfElement[currentnum]++;
}
//依次将桶中的数据 合到数组中
int indexArr = 0;
int indexBucket = 0;
for (int j = 0; j < bucketOfElement.length; j++) {
while (bucketOfElement[j] != 0) {
arr[indexArr] = bucket[j][indexBucket];
indexArr += 1;
indexBucket += 1;
bucketOfElement[j]--;
}
indexBucket = 0;
}
}
}
希尔排序
1.将数的个数设为n，取奇数k=n/2，将下标差值为k的书分为一组，构成有序序列。
2.再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
3.重复第二步，直到k=1执行简单插入排序。
public static int[] shellSort(int[] arr) {
int temp = 0;
//插入时 采用交换法
for (int l = arr.length / 2; l > 0; l /= 2) {
//遍历各组中所有的元素，（共有 l 组，每组有数个元素）。 l 为步长
for (int i = l; i < arr.length; ++i) {
for (int j = i; j - l >= 0; j -= l) {
//如果当前的元素大于 加上步长后的那个元素的话就 交换位置
if (arr[j] < arr[j - l]) {
temp = arr[j];
arr[j] = arr[j - l];
arr[j - l] = temp;
}
}
}
}
return arr;
}
归并排序
1.选择相邻两个数组成一个有序序列。
2.选择相邻的两个有序序列组成一个有序序列。
3.重复第二步，直到全部组成一个有序序列。
/**
* 归并排序
* @param arr 需要排序的数组
* @param left 数组左边的索引
* @param right 数组右边的索引
*/
public void mergetSort(int[] arr , int left ,int right){
if (left<right){
int mid = (left+right)/2;
//向坐递归
mergetSort(arr,left,mid);
//向右递归
mergetSort(arr,mid+1,right);
//合并递归后的
merget(arr,left,mid,right);
}
}
/**
* 合并的方法
*
* @param arr 需要排序的数组
* @param left 左边有序序列的初始索引
* @param mid 中间序列的索引
* @param right 右边序列的索引
*/
public void merget(int[] arr,int left,int mid,int right){
int l =left;//初始化l，左边有序序列的初始索引
int m = mid+1; //初始化m，右边有序序列的初始索引
int index=0;//指向tempArr数组的当前索引
//做中转的数组
int[] tempArr=new int[right-left+1];
//比较两个素组
//先把左右两边 有序的 按照规则填充到temp数组中
//直到 有一边的数组已经处理完毕
while (l<=mid&&m<=right){
//如果左边有序序列的当前元素 小于右边的有序序列的当前元素
//即将左边的当前元素，填充到team
//让后 l++ index++
if (arr[l]<arr[m]){
tempArr[index]=arr[l];
l++;
}else{ //反之 将右边的当前元素 填充到team数组中
tempArr[index]=arr[m];
m++;
}
index++;
}
//把剩余数组 依次填充到tempArr 数组中
//如果左边有剩余，就把左边的全部加进去
while (l<=mid){
tempArr[index]=arr[l];
l++;
index++;
}
//如果右边有剩余，就把右边的全部加进去
while(m<=right){
tempArr[index]=arr[m];
m++;
index++;
}
//将tempArr中 有序的元素，添加到 arr数组中
int i=0;
while (left<=right){
arr[left]=tempArr[i];
i++;
left++;
}
}
插入排序
1.将第一个数和第二个数排序，然后构成一个有序序列
2.将第三个数插入进去，构成一个新的有序序列。
3.对第四个数、第五个数……直到最后一个数，重复第二步。
/**
* 插入排序
*
* @param arr 需要排序的数组
*/
public void insertSort(int[] arr) {
for (int i = 1; i < arr.length; ++i) {
for (int j = 0; j < i; ++j) {
if (arr[i]<arr[j]){
arr[j]^=arr[i];
arr[i]^=arr[j];
arr[j]^=arr[i];
}
}
}
}
冒泡排序
1.将序列中所有元素两两比较，将最大的放在最后面。
2.将剩余序列中所有元素两两比较，将最大的放在最后面。
3.重复第二步，直到只剩下一个数。
/**
* 冒泡排序
*
* @param arr 待排序的数组
*/
public void bubbleSort(int[] arr) {
for (int i = arr.length; i > 0; --i) {
for (int j = 1; j < i; ++j) {
if (arr[j] < arr[j - 1]) {
//交换位置
arr[j] ^= arr[j - 1];
arr[j - 1] ^= arr[j];
arr[j] ^= arr[j - 1];
}
}
}
}
堆排序
思路：
1.将序列构建成大顶堆。
2.将根节点与最后一个节点交换，然后断开最后一个节点。
3.重复第一、二步，直到所有节点断开。
/**
* 堆排序
*
* @param arr 待排序的数组
*/
public void headSort(int[] arr) {
int len = arr.length - 1;
//利用循环 排成大顶堆 (叶子结点 小于父节点 满足a[i]>a[i*2+1]&&a[i]>a[i*2+2]条件)
for (int i = len / 2 - 1; i >= 0; --i) {
swap(arr, i, len);
}
int temp = 0;
//排完序之后堆顶一定是最大的数，让后把最大的数放到数组最后面断开节点
for (; len > 0; len--) {
temp = arr[len];
arr[len] = arr[0];
arr[0] = temp;
swap(arr, 0, len - 1);
}
}
public void swap(int[] arr, int k, int len) {
for (int i = k * 2 + 1; i <= len; i = i * 2 + 1) {
if (i < len && arr[i] < arr[i + 1]) i++;
if (arr[i] > arr[k]) {
int temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
k = i;
}
}
}
快速排序
思路：
1.选择第一个数为p，小于p的数放在左边，大于p的数放在右边。
2.递归的将p左边和右边的数都按照第一步进行，直到不能递归。
/**
* 快速排序
*
* @param arr 需要排序的数组
* @param left 0
* @param right 数组的长度-1
*/
public void fastSort(int[] arr, int left, int right) {
int l = left;
int r = right;
int mid = (l + r) / 2;
while (l < r) {
//在左边找到大于的值
while (arr[l] < arr[mid]) l++;
//在右边找到小于的值
while (arr[r] > arr[mid]) r--;
//如果 l>= r ,则说明 mid左边全是小于arr[mid]的数，右边全是大于arr[mid]的数
if (l >= r) break;
//交换位置
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完之后， 发现arr[l] == arr[mid] 则r-- ，前移
if (arr[l] == arr[mid]) {
r -= 1;
}
//如果交换完之后， 发现arr[r]==arr[mid] 则l--,往后移
if (arr[r] == arr[mid]) {
l += 1;
}
}
// 如果 l == r, 必须l++, r--, 否则为出现栈溢出
if (l == r) {
l++;
r--;
}
//向右递归
if (l < right) fastSort(arr, l, right);
//向左递归
if (r > left) fastSort(arr, left, r);
}
