1.冒泡排序
package Sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int [] a = {1,100,234,44,3,2,4,5};
bubbleSort(a,a.length+1);
System.out.println(Arrays.toString(a));
}
public static int[] bubbleSort(int[] A, int n) {
for (int i=0;i<A.length;i++){
for (int j=i+1;j<A.length;j++){
if (A[i] > A[j]){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
}
return A;
}
}
2.快速排序
package Sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int A[] = {1,6,9, 2, 3, 1, 5, 4 };
quickSort(A, 0, 7);
System.out.println(Arrays.toString(A));
}
public static void quickSort(int[] A, int left, int right) {
if (left < right) {
// 一次划分
int mid = partion(A, left, right);
quickSort(A, 0, mid - 1);
quickSort(A, mid + 1, right);
}
}
public static void swap(int[] A, int l, int r) {
int tmp = A[l];
A[l] = A[r];
A[r] = tmp;
}
public static int partion(int[] a, int left, int right) {
// 轴值，默认选取数组的第一个数字
while (left < right) {
while (left < right && a[left] <= a[right]) {
right--;
}
if (left<right){
swap(a, left, right);
}
while (left < right && a[left] <= a[right]) {
left++;
}
if (left<right){
swap(a, left, right);
}
}
return left;
}
}
3.插入排序
package Sort;
public class InsertionSort {
public int[] insertionSort(int[] A, int n) {
int i, j, temp;
for(i = 1; i < n; i++){
temp = A[i];
for(j = i; j > 0 && A[j - 1] > temp; j-- ){
A[j] = A[j - 1];
}
A[j] = temp;
}
return A;
}
}
3.1希尔排序（插入排序的一种）
package Sort;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] a = { 54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28 };
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] a) {
// 设置步长，默认为数组长度的一半
int step = a.length / 2;
while (step >= 1) {
for (int i = step; i < a.length; i += step) {
int tmp = a[i];
int j;
for (j = i; j > 0 && a[j - step] > tmp; j -= step) {
a[j] = a[j - step];//元素后移
}
a[j] = tmp;//插入的位置，注意此时j在for循环中已经进行了一次--
}
step /= 2;
}
}
}
4.选择排序
package Sort;
public class SelectionSort {
public int[] selectionSort(int[] A, int n) {
// write code here
for (int i = 0; i < n - 1; i++) {
int index = i;
int j;
// 找出最小值得元素下标
for (j = i + 1; j < n; j++) {
if (A[j] < A[index]) {
index = j;
}
}
int tmp = A[index];
A[index] = A[i];
A[i] = tmp;
}
return A;
}
}
5. 归并排序
package Sort;
public class MergeSort {
public static void main(String[] args) {
int[] A = { 1, 4, 3, 2, 5 };
mergeSort(A, 5);
for (int i = 0; i < A.length; i++) {
System.out.println(A[i]);
}
}
public static int[] mergeSort(int[] A, int n) {
// write code here
sort(A, 0, n - 1);
return A;
}
public static void sort(int[] A, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(A, left, mid);
sort(A, mid + 1, right);
merge(A, left, mid, right);
}
}
public static void merge(int[] A, int left, int mid, int right) {
// 临时数组
int n = right - left + 1;
int[] tmpArr = new int[n];
int l = left;
int r = mid + 1;
int t = 0;// 临时数组下标元素
// 比较两子序列元素的大小
while (l <= mid && r <= right) {
if (A[l] < A[r]) {
tmpArr[t++] = A[l++];
} else {
tmpArr[t++] = A[r++];
}
}
// 剩余的加入临时数组
while (l <= mid) {
tmpArr[t++] = A[l++];
}
// 剩余的加入临时数组
while (r <= right) {
tmpArr[t++] = A[r++];
}
// 把临时数组元素放回原数组
for (int i = 0; i < t; i++) {
A[left + i] = tmpArr[i];
}
}
}
6.堆排序
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] a = { 2, 5, 9, 6, 1, 4, 8, 7, 12, 50 };
sort(a);
System.out.println(Arrays.toString(a));
}
public static void sort(int[] a) {
int len = a.length;
for (int i = 0; i < len - 1; i++) {
// 建堆
buildHeap(a, len - 1 - i);
// 交换堆顶元素和最后一个元素
swap(a, 0, len - 1 - i);
}
}
private static void swap(int[] a, int i, int j) {
// TODO Auto-generated method stub
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void buildHeap(int[] a, int lastIndex) {
// 从最后一个节点的父节点开始
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
// 当前节点存在子节点
while (i * 2 + 1 <= lastIndex) {
// 左节点下标值
int l = i * 2 + 1;
// 右结点下标值
int r = i * 2 + 2;
// 默认左节点为最大值
int biggerIndex = l;
// 存在右结点
if (l < lastIndex) {
// 右结点的值比左节点大
if (a[r] > a[l]) {
biggerIndex = r;
}
}
// 当前节点的值比孩子节点的最小值小，交换
if (a[i] < a[biggerIndex]) {
swap(a, i, biggerIndex);
// 把最大值下标赋给当前节点，进入下一次while循环判断
i = biggerIndex;
} else {
break;
}
}
}
}
}
7.计数排序
8.基数排序
9.桶排序