Sort
排序是重要的一种操作。本文主要介绍各种常用的排序算法。
包括
插入排序（直接插入。希尔排序）
交换排序（冒泡 快排）
选择排序（直接选择 堆排序）
归并排序
外部排序
1.插入排序
直接插入排序
package sort;
public class InsertionSort {
public static void sort(int[] a){
int n=a.length;
int j=0;
for(int i=0;i<n;i++){
int tmp=a[i];
for(j=i;j>0 && tmp<a[j-1];j--){
a[j]=a[j-1];
}
a[j]=tmp;
}
}
public static void main(String[] args) {
int[] a={9,2,4,7,4,10,3,8};
sort(a);
for(int i:a){
System.out.print(i+" ");
}
}
}
希尔排序
package sort;
public class ShellSort {
public static void sort(int[] a){
int n=a.length;
int j;
for(int gap=n/2;gap>0;gap/=2){
for(int i=gap;i<a.length;i++){
int tmp=a[i];
for(j=i;j>=gap&&tmp<a[j-gap];j=j-gap){
a[j]=a[j-gap];
}
a[j]=tmp;
}
}
}
public static void main(String[] args) {
int[] a={9,2,4,7,4,10,3,8};
sort(a);
for(int i:a){
System.out.print(i+" ");
}
}
}
2.交换排序
冒泡排序
package sort;
public class BubbleSort {
public static void sort(int[] a){
int n=a.length;
for(int i=0;i<n;i++){
for(int j=0;j<n-1-i;j++){
if(a[j]>a[j+1]){
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
public static void main(String[] args) {
int[] a={2,4,7,4,10,3,8};
sort(a);
for(int i:a){
System.out.print(i+" ");
}
}
}
快排
package sort;
/**
* ����
* @author neuly
*
*/
public class QuickSort {
public static int[] swap(int[] s, int l,int r){
//���м�����͵�һ�������н���
int tmp=s[l];
s[l]=s[(r-l)/2];
s[(r-l)/2]=tmp;
return s;
}
public static void quickSort(int[] s, int l,int r){
if(l<r){
int i=l,j=r,x=s[l];
while(i<j){
while(i<j&&s[j]>=x) j--;
if(i<j) s[i++]=s[j];
while(i<j&&s[i]<=x) i++;
if(i<j) s[j--]=s[i];
}
s[i]=x;
quickSort(s, l, i-1);
quickSort(s, i+1, r);
}
}
public static void sort(int[] a){
quickSort(a, 0, a.length-1);
}
public static void main(String[] args) {
int[] a={2,4,7,4,10,3,8};
sort(a);
for(int i:a){
System.out.print(i+" ");
}
}
}
3.选择排序
堆排序
package sort;
public class HeapSort {
private static int leftchild(int i){
return 2*i+1;
}
private static void percDown(int[] a, int i,int n){
int child;
int tmp;
for(tmp=a[i];leftchild(i)<n;i=child){
child=leftchild(i);
if(child!=n-1&&a[child]<a[child+1]){
child++;
}
if(tmp<a[child]){
a[i]=a[child];
}else{
break;
}
}
a[i]=tmp;
}
public static void sort(int[] a){
//建立堆
for(int i=a.length/2;i>=0;i--){
percDown(a, i, a.length);
}
//堆排序
for(int i=a.length-1;i>0;i--){
int temp = a[i];
a[i] = a[0];
a[0] = temp;
percDown(a, 0, i);
}
}
public void print(int[] list,int begin,int end){
for(int i=0;i<begin;i++) System.out.print("\t");
for(int i=begin;i<=end;i++) System.out.print(list[i] + "\t");
System.out.println();
}
public static void main(String[] args) {
// ��ʼ��һ������
int[] array = {
1, 3, 4, 5, 2, 6, 9, 7, 8, 0
};
// ���ÿ�������
HeapSort heap = new HeapSort();
System.out.print("����ǰ:\t");
heap.print(array, 0, array.length - 1);
heap.sort(array);
System.out.print("�����:\t");
heap.print(array, 0, array.length - 1);
}
}
4.归并排序
思路：
将数组氛围left right两部分 分别排序，再merge。
package sort;
import java.util.Arrays;
public class MergeSort {
private static void sort(int[]a,int[]tmpArray, int left,int right){
if(left<right){
int mid=(left+right)/2;
sort(a,tmpArray,left, mid);
sort(a,tmpArray, mid+1, right);
merge(a,tmpArray,left,mid+1,right);
}
}
private static void merge(int[]a,int[]tmpArray,int leftPos,int rightPos,int rightEnd){
int numElements=rightEnd-leftPos+1;
int leftEnd=rightPos-1;
int tmpPos=leftPos;
while(leftPos<=leftEnd&&rightPos<=rightEnd){
if(a[leftPos]<a[rightPos]){
tmpArray[tmpPos++]=a[leftPos++];
}else{
tmpArray[tmpPos++]=a[rightPos++];
}
}
while(leftPos<=leftEnd) tmpArray[tmpPos++]=a[leftPos++];
while(rightPos<=rightEnd) tmpArray[tmpPos++]=a[rightPos++];
for(int i=0;i<numElements;i++,rightEnd--){
a[rightEnd]=tmpArray[rightEnd];
}
}
public static void mergeSort(int[] a){
int[] tmpArray= new int[a.length];
sort(a,tmpArray, 0, a.length-1);
}
public static void main(String[] args) {
// ��ʼ��һ������
int[] array = {
1, 3, 4, 5, 2, 6, 9, 7, 8, 0
};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
}
5.外部排序
排序方法。
二路归并
总结
