// 冒泡排序
public static void bubbleSort(int arr[]) {
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]) {
int temp = arr[j];
arr[j]=arr[j 1];
arr[j 1]=temp;
}
}
}
}
代码语言：javascript复制
//选择排序
public static void selectSort(int arr[]){
for(int i = 0; i < arr.length-1; i ){
int min = i;
for(int j = i 1; j <arr.length ;j ){
if(arr[j]<arr[min]){
min = j;
}
}
if(min!=i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
代码语言：javascript复制
// 插入排序
public static void insertsort(int arr[]){
for (int i=1;i<arr.length;i ) {
for(int j=i;j>0&&(arr[j]<arr[j-1]);j--) {
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
}
代码语言：javascript复制
// 希尔排序
public static void shellSort(int arr[]){
int gap = arr.length;
while (true) {
gap /= 2; //增量每次减半
for (int i = 0; i < gap; i ) {
for (int j = i gap; j < arr.length; j = gap) {//这个循环里其实就是一个插入排序
int temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp) {
arr[k gap] = arr[k];
k -= gap;
}
arr[k gap] = temp;
}
}
if (gap == 1)
break;
}
}
代码语言：javascript复制
// 归并排序
public static int[] mergeSort(int arr[], int l, int r) {
if (l == r)
return new int[] { arr[l] };
int mid = l (r - l) / 2;
int[] leftArr = mergeSort(arr, l, mid); //左有序数组
int[] rightArr = mergeSort(arr, mid 1, r); //右有序数组
int[] newNum = new int[leftArr.length rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m ] = leftArr[i] < rightArr[j] ? leftArr[i ] : rightArr[j ];
}
while (i < leftArr.length)
newNum[m ] = leftArr[i ];
while (j < rightArr.length)
newNum[m ] = rightArr[j ];
return newNum;
}
代码语言：javascript复制
// 快速排序
public static int[] quickSort(int arr[],int start,int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (i<j) {
while ((i<j)&&(arr[j]>pivot)) {
j--;
}
while ((i<j)&&(arr[i]<pivot)) {
i ;
}
if ((arr[i]==arr[j])&&(i<j)) {
i ;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i-1>start) arr=quickSort(arr,start,i-1);
if (j 1<end) arr=quickSort(arr,j 1,end);
return (arr);
}
代码语言：javascript复制
// 基数排序
public static void radixSort(int[] arr, int d){ //d表示最大的数有多少位
int k = 0;
int n = 1;
int m = 1; //控制键值排序依据在哪一位
int[][]temp = new int[10][arr.length]; //数组的第一维表示可能的余数0-9
int[]order = new int[10]; //数组orderp[i]用来表示该位是i的数的个数
while(m <= d) {
for(int i = 0; i < arr.length; i ) {
int lsd = ((arr[i] / n) % 10);
temp[lsd][order[lsd]] = arr[i];
order[lsd] ;
}
for(int i = 0; i < 10; i ) {
if(order[i] != 0)
for(int j = 0; j < order[i]; j ) {
arr[k] = temp[i][j];
k ;
}
order[i] = 0;
}
n *= 10;
k = 0;
m ;
}
}
代码语言：javascript复制
// 堆排序
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i 1; k < length; k = 2 * k 1) { //2*i 1为左子树i的左子树(因为i是从0开始的),2*k 1为k的左子树
// 让k先指向子节点中最大的节点
if (k 1 < length && array[k] < array[k 1]) { //如果有右子树,并且右子树大于左子树
k ;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
代码语言：javascript复制
// 计数排序
public static int[] countSort(int arr[]){
int b[] = new int[arr.length];
int max = arr[0],min = arr[0];
for(int i:arr){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//这里k的大小是要排序的数组中，元素大小的极值差 1
int k=max-min 1;
int c[]=new int[k];
for(int i=0;i<arr.length; i){
c[arr[i]-min] =1;//优化过的地方，减小了数组c的大小
}
for(int i=1;i<c.length; i){
c[i]=c[i] c[i-1];
}
for(int i=arr.length-1;i>=0;--i){
b[--c[arr[i]-min]]=arr[i];//按存取的方式取出c的元素
}
return b;
}
