最简单但是也是最没用的一种算法。（时间复杂度N方，还不稳定）。
时间复杂度：N方
空间复杂度：1
基本思想是：第一次从 arr[0]~arr[n-1]中选取最小值，与 arr[0]交换；第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换；第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。
public class 选择排序 {
public static void main(String[] args) {
int arr[] = {1,3,2,4,5};
//返回数组的字符串形式
System.out.println("排序前："+Arrays.toString(arr));
Arrays.toString(arr)
System.out.println("排序后："+Arrays.toString(arr));
}
//选择排序算法
public static void SelectSort(int [] arr){
for(int i = 0;i < arr.length-1;i++){
int minPos = i;
for(int j = i+1;j < arr.length;j++){
if(arr[minPos] > arr[j]){
minPos = j;
}
//交换两个数
swap(arr,minPos,i);
}
System.out.println(Arrays.toString(arr));
}
//交换两个数
public static void swap(int [] arr){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
class DataChecker{
public static int [] Random(){
Random r = new Random();
int [] arr = new int[10000];
for(int i=0;i<arr.length;i++){
arr[i]=r.nextInt(10000);
}
return arr;
}
public static void Check(){
int arr [] = Random();
int arr2 [] = new int [arr.length];
System.arraycopy(arr,0,arr2,0,arr.length);
Arrays.sort(arr);
SelectSort(arr2);
boolean flag=true;
for(int i =0;i<arr.length;i++){
if(arr[i]!=arr2[i]){
flag=false;
break;
}
}
if(flag){
System.out.println("正确");
}
else{
System.out.println("错误");
}
}
//选择排序算法
public static void SelectSort(int [] arr){
for(int i = 0;i < arr.length-1;i++){
int minPos = i;
for(int j = i+1;j < arr.length;j++){
if(arr[minPos] > arr[j]){
minPos = j;
}
//交换两个数
swap(arr,minPos,i);
}
System.out.println(Arrays.toString(arr));
}
//交换两个数
public static void swap(int [] arr){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
选择排序
对数器
在第二个循环中，不能直接交换两个数，会改变数组中的元素，定义一个mindex代替循环变量j。
if(arr[minPos]>arr[j]){//前面的并不是最小值，交换两个值
minPos=j;
}
//交换两个数
swap(arr,minPos,i);
冒泡排序：从前向后遍历，依次比较相邻元素的值，若发现相邻元素则交换，这样遍历完一次可以让最大元素放在最后。
优化：在排序的过程中，各元素的位置不断的靠近自己的位置，如果在一趟比较下来没有发生果交换，就说明序列已经排好序。
package 排序算法;
import java.util.Arrays;
public class 冒泡排序 {
public static void main(String[] args) {
int arr[]={3,9,-1,10,20};
String s = Arrays.toString(arr);//返回数组的字符串形式。
System.out.println(s);
bubblesort(arr);
String ss = Arrays.toString(arr);
System.out.println(ss);
}
public static void bubblesort(int[] arr){
int temp=0;//临时变量
boolean flag=false;//标识变量，表示是否发生过交换
for(int i=0;i<arr.length-1;i++){//表示要进行N-1趟
for(int j=0;j<arr.length-1-i;j++){//每一次遍历要将大的数放在后面
/*
//如果是逆序，则交换两个元素
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
*/
if(arr[j]>arr[j+1]){
flag=true;
arr[j]=arr[j]^arr[j+1];
arr[j+1]=arr[j]^arr[j+1];
arr[j]=arr[j]^arr[j+1];
}
}
//优化
if(!flag){//在一趟中没有发生交换
break;
}
else{
flag=false;//重置flag，进行下次判断
}
}
}
}
冒泡排序算法
Arrarys类
String s = Arrays.toString(arr);//返回数组的字符串形式。
开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
//插入排序
public static void insertsort(int[] arr){
//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
for(int i=1;i<arr.length;i++){
// 记录要插入的数据
int temp=arr[i];
// 从已经排序的序列最右边的开始比较，找到比其小的数
int j=i;
while (j>0&&temp<arr[j-1]){
arr[j]=arr[j-1];//用于查找前面是否有更小的值
j--;
}
// 存在比其小的数，插入
if(j!=i){
arr[j]=temp;
}
}
}
插入排序
注意在前面的有序列表中找到要插入的位置。
简单排序存在的问题：当我们插入的数较小时，后移的次数明显增多，对效率有很大影响。
//希尔排序
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}
在排序的数列中，我们首先找一个数为基准，所有大于基准的数放在右边，小于基准的数全部放在左边，最后将基准数归位。
//快速排序
public static void quickSort(int [] arr,int left,int right){
if(left>right){
return;
}
int i=left;
int j=right;
int t;//做临时变量，用来交换
int temp=arr[left];
while(i!=j){
while(arr[j]>=temp&&i<j){
j--;
}
while(arr[i]<=temp&&i<j){
i++;
}
if(i<j){//表示哨兵还没有相遇，交换两个数
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}
arr[left]=arr[i];
arr[i]=temp;
quickSort(arr,left,i-1);//向左递归
quickSort(arr,i+1,right);//向右递归
return;
}
时间复杂度：NlgN
空间复杂度：O（N)
附加知识点：归并排序是稳定的，在java中经常使用。在Java中，对于Java对象的排序一般要求都是稳定的。在java中，使用TimMeragr(改进的归并排序) 对一个数组分多个组进行排序，最后两两进行归并排序。在小组内部使用二分插入排序。
需要定义三个指针，一个临时数组temp；指向左边数组的指针i；指向右边数组的指针j；指向临时数组的指针k。
比较左右两边的数值，数值小的赋值给temp，然后自身向后++。当一边结束后，将另一边剩下的值全部赋值给temp即可。
//归并排序
public static void mergeSort(int [] arr,int left,int right){
//只有一个元素
if(left==right){
return;
}
//将数组分成两半
int mid=left+(right-left)/2;
//左边排序
mergeSort(arr,left,mid);
//右边排序
mergeSort(arr,mid+1,right);
//归并两个有序数组
merge(arr,left,mid+1,right);
}
public static void merge(int [] arr,int leftPtr,int rightPtr,int rightBound){
//将需要的数组一分为二
int mid=rightPtr-1;
int i=leftPtr;
int j=rightPtr;
int k=0;
int [] temp=new int[rightBound-leftPtr+1];
//循环将数组有序添加到临时数组
while(i <= mid && j <= rightBound){//可以用三元运算符写
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
/*
if(arr[i] <= arr[j]){
temp[k] = arr[i];
i++;
k++;
}
else{
temp[k] = arr[j];
j++;
k++;
}
*/
}
//判断那边的数组没有遍历完
while(i <= mid) temp[k++] = arr[i++];
while(j <= rightBound) temp[k++] = arr[j++];
//将临时数组的值复制到arr数组
for(int m=0;m<temp.length;m++) arr[leftPtr+m]=temp[m];
}
原文：https://www.cnblogs.com/nj123/p/14256789.html