冒泡排序
public void sort(int[] a) {
for(int i=0;i<a.length-1;i++){
boolean flag = true;
for(int j=0;j<a.length-i-1;j++){
if(a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = false;
}
}
if(flag)
break;
}
}
选择排序
public void sort(int[] a) {
for(int i=0;i<a.length-1;i++){
int index = i;
for(int j=i+1;j<a.length;j++){
if(a[index] > a[j])
index = j;
}
if(index > i){
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
}
插入排序
public void sort(int[] a) {
for(int i=1;i<a.length;i++){
int temp = a[i];
int j = i-1;
while(j>=0 && temp<a[j]){
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
希尔排序
public void sort(int[] a) {
for(int g=a.length/2;g>=1;g/=2){ // 缩小增量
for(int i=g;i<a.length;i++){ // 插入排序
int temp = a[i];
int j = i-g;
while(j>=0 && temp<a[j]){
a[j+g] = a[j];
j-=g;
}
a[j+g] = temp;
}
}
}
计数排序
public void sort(int[] a) {
int[] b= new int[a.length];
int max = a[0], min = a[0];
for (int i : a) {
max = Math.max(max, i);
min = Math.min(min, i);
}
int k = max - min + 1;
int[] c = new int[k];
for (int i = 0; i < a.length; ++i) {
c[a[i] - min] += 1;
}
for (int i = 1; i < c.length; ++i) { // 保存元素位置
c[i] = c[i] + c[i - 1];
}
for (int i = a.length - 1; i >= 0; --i) { // 从后往前遍历，保证稳定排序
b[--c[a[i] - min]] = a[i];
}
System.arraycopy(b, 0, a, 0, a.length);
}
基数排序
public void sort(int[] a, int digit) {
double max = Math.pow(10, digit);
for (int exp = 1; exp < max; exp *= 10) {
int[] temp = new int[a.length];
int[] buckets = new int[10];
for (int value : a) {
buckets[(value / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
buckets[i] += buckets[i - 1];
}
for (int i = a.length - 1; i >= 0; i--) {
temp[--buckets[(a[i] / exp) % 10]] = a[i];
}
System.arraycopy(temp, 0, a, 0, a.length);
}
}
堆排序
private void heapify(int[] a, int i, int n){
while(2*i+1 < n){
int j = 2*i+1;
if(j+1 < n && a[j] < a[j+1]) j++;
if(a[i] < a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
}
else
break;
}
}
public void sort(int[] a) {
int n = a.length;
for(int i=n/2-1;i>=0;i--){
heapify(a, i ,n);
}
for(int i=n-1;i>0;i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, 0, i);
}
}
归并排序
public void sort(int[] a) {
mergeSort(a, 0, a.length - 1);
}
private void mergeSort(int[] a, int left, int right) {
if(left >= right) {
return;
}
int mid = left + ((right - left) >> 1);
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
private void merge(int[] a, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
while(p1 <= mid && p2 <= right) {
temp[i++] = a[p1] <= a[p2] ? a[p1++] : a[p2++];
}
while(p1 <= mid) {
temp[i++] = a[p1++];
}
while(p2 <= right) {
temp[i++] = a[p2++];
}
for(i = 0; i < temp.length; i++) {
a[left + i] = temp[i];
}
}
快速排序
public void sort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private void quickSort(int[] a, int i, int j) {
if (i < j) {
int q = partition(a, i, j);
quickSort(a, i, q-1);
quickSort(a, q+1, j);
}
}
private int partition(int[] a, int i, int j) {
int left = i;
int right = j;
int pivot = a[i];
while (left <= right) {
while (left <= right && a[left] <= pivot) left++;
while (left <= right && a[right] > pivot) right--;
if (left < right) {
int temp = a[left];
a[left] = a[right];
a[right] = temp;
}
}
a[i] = a[right];
a[right] = pivot;
return right;
}
桶排序
public void sort(int[] a) {
int max = a[0], min = a[0];
for (int i = 0; i < a.length; i++) {
max = Math.max(max, a[i]);
min = Math.min(min, a[i]);
}
int bucketNum = (max - min) / a.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
for (int i = 0; i < a.length; i++) {
int num = (a[i] - min) / a.length;
bucketArr.get(num).add(a[i]);
}
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
int k = 0;
for (int i = 0; i < bucketArr.size(); i++) {
for (int j = 0; j < bucketArr.get(i).size(); j++) {
a[k++] = bucketArr.get(i).get(j);
}
}
}
