一、选择排序
思路：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与第二个元素交换位置。不断进行这样的操作，直到遍历完整个数组。
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性（两个相等元素的绝对位置交换前后是否发生改变）：不稳定
public static void SelectSort(int[] arr){
int minIndex;
//依此遍历找剩下元素的最小
for (int i=0;i<arr.length;i++){
minIndex=i;
for (int j=i+1;j<arr.length;j++){
if (arr[j]<arr[minIndex]){
minIndex=j;
}
}
//交换元素
if (minIndex!=i){
int tmp=arr[minIndex];
arr[minIndex]=arr[i];
arr[i]=tmp;
}
}
}
二、冒泡排序
思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
时间复杂度：O（n^2）
空间复杂度：O（1）
稳定性：稳定
public static void bubbleSort(int[] arr) {
//该轮是否排序了
boolean isSort = true;
//如果上一轮没有发生交换，直接跳出循环
for (int i = 0; i < arr.length && isSort; i++) {
isSort = false;
for (int j = 1; j < arr.length - i; j++) {
if (arr[j - 1] > arr[j]) {
isSort = true;
//交换元素
int tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
}
}
三、插入排序
思路：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
时间复杂度：O（N）~O（N^2）和初始顺序有关
空间复杂度：O（1）
稳定性：稳定
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//寻找适合的位置插入
if (arr[i] < arr[i - 1]) {
int tmp = arr[i];
int j;
for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
}
四、希尔排序
思路：插入排序只能交换相邻的元素，对于大规模的数组，其插入排序很慢，希尔排序使用插入排序对时间间隔h的序列进行排序，通过不断减小h，最后令h=1。
时间复杂度：依赖于增量序列，优于插入排序
空间复杂度：O（1）
稳定性：不稳定
public static void shellSort(int[] arr) {
//初始间隔d，一直到1
for (int d = arr.length / 2; d > 0; d = d / 2) {
//从d开始
for (int i = d; i < arr.length; i++) {
for (int j = i - d; j >= 0; j -= d) {
if (arr[j + d] < arr[j]) {
int tmp = arr[j + d];
arr[j + d] = arr[j];
arr[j] = tmp;
}
}
}
}
}
五、快速排序
思路：快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
时间复杂度：O（NlogN）
空间复杂度：O（logN）
稳定性：不稳定
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
//确定切分元素
int stard = arr[start];
int low = start, high = end;
while (low < high) {
while (low < high && arr[high] >= stard) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] < stard) {
low++;
}
arr[high] = arr[low];
}
arr[low] = stard;
//处理前面的
quickSort(arr, start, low - 1);
//后面
quickSort(arr, low + 1, end);
}
}
六、归并排序
思路：归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
时间复杂度：O（NlogN）
空间复杂度：O（N）
稳定性：稳定
public static void mergeSort(int[] arr,int low,int high){
int middle=(low+high)/2;
if (low<high){
//处理左边
mergeSort(arr,low,middle);
//处理右边
mergeSort(arr,low+1,high);
//排序
merge(arr,low,middle,high);
}
}
/**
*@description
* 将两个已经排序的数组并成一个
*@author lugton
*@date 2020/3/23
*@return
*/
public static void merge(int[] arr,int low,int middle,int high){
int i=low,j=middle+1;
int[] tmp=new int[arr.length];
//复制辅助数组
for (int k=low;k<=high;k++){
tmp[k]=arr[k];
}
for (int k=low;k<=high;k++){
//前面数组已经排完
if (i>middle){
arr[k]=tmp[j++];
}else if (j>high){
//后面数组已经排完
arr[k]=tmp[i++];
}else if (tmp[i]<=tmp[j]){
arr[k]=tmp[i++];
}else {
arr[k]=tmp[j++];
}
}
}
七、堆排序
思路：构建大顶堆，然后依此将堆顶放入数组，从后往前放。
时间复杂度：O（NlogN）
空间复杂度：O（1）
稳定性：不稳定
public static void heapSort(int[] arr){
//开始位置是最后一个非叶子节点，也就是最后一个节点的父节点
int start=(arr.length-1)/2-1;
//调整为大顶堆
for (int i=start;i>=0;i--){
maxHeap(arr,arr.length,i);
}
//把数组第0个和堆中最后一个交换位置
for (int i=arr.length-1;i>0;i--){
int tmp=arr[0];
arr[0]=arr[i];
arr[i]=tmp;
maxHeap(arr,i,0);
}
}
public static void maxHeap(int[] arr,int size,int index){
//左子节点
int left=2*index+1;
int right=2*index+2;
int max=index;
//找出最大的节点
if (left<size && arr[left]>arr[max]){
max=left;
}
if (right<size && arr[right] > arr[max]){
max=right;
}
//交换位置
if (max!=index){
int tmp=arr[index];
arr[index]=arr[max];
arr[max]=tmp;
//交换位置以后，可能会破坏之前的堆，所以要重新进行排序
maxHeap(arr,size,max);
}
}
也可以利用优先队列构建小顶堆
public static void heap(int[] arr){
//小顶堆
PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
for (int num:arr
) {
priorityQueue.add(num);
}
for (int i=0;i<arr.length;i++){
arr[i]=priorityQueue.poll();
}
}
八、基数排序
思路：数字都是由0-9组成的，所以可以用10个桶来进行排序。先依据序列的个为分配到指定的桶中，然后再对十位...百位...做相应排序。
时间复杂度：O（n）
空间复杂度：O（n+k）k为桶的数量
稳定性：稳定
/**
* @return
* @description digit 最多有多少位数字
* @author lugton
* @date 2020/6/26
*/
public void randix(int[] arr, int digit) {
//10个桶
int radix = 10;
int begin = 0, end = arr.length - 1;
int i = 0, j = 0;
//存放每个桶的数据个数
int[] count = new int[radix];
int[] bucket = new int[end - begin + 1];
//按照从低位到高位的顺序进行排序 也就是从个位开始
for (int d = 1; d <= digit; d++) {
//初始化
for (i = 0; i < radix; i++) {
count[i] = 0;
}
//统计每个桶要装入数据的个数
for (i = begin; i <= end; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
//每个桶的右边界索引
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
//数字依次入桶
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
//放入桶的对应位置
bucket[count[j] - 1] = arr[i];
//索引对应的也要减一位
count[j]--;
}
//返回按个位排序的数组
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
/**
* @return
* @description 获取数字x第d位上的数字
* @author lugton
* @date 2020/6/26
*/
public int getDigit(int x, int d) {
while (--d > 0) {
x = x / 10;
}
return x % 10;
}
九、二分查找
public static void BinarySearch(int[] arr,int target){
int begin=0;
int end=arr.length-1;
int index=-1;
int mid=(begin+end)/2;
while (true){
if (target==arr[mid]){
index=mid;
break;
}else {
if (target<arr[mid]){
end=mid-1;
}else {
begin=mid+1;
}
}
mid=(begin+end)/2;
}
System.out.println("index:"+index);
}
