java实现的排序
public class Sort {
//插入排序算法策略：排序值列中的前2个值，并在必要时交换它们。
//在相对于前2个值（有序的）的适当位置插入值列的第三个值。
//然后，在相对于前3个值（有序的）的适当位置插入值列的第4个值。
//每进行一次插入操作，有序子集中的数值个数将递增1。
//重复该过程，直至值列中的所有值都按照次序排列为止。插入过程需要移动数组中的其他值，为插入的元素腾出存储空间。
public static void insert(int[] data) {
int length = data.length;
for(int i=1; i<length;i++) {
int key = data[i];
int index = i;
while(index>0 && data[index-1]>key) {
data[index] = data[index -1];
index--;
}
data[index] = key;
}
//for(int i=1; i<data.length; i++) {
//int j = i;
//int temp = data[i];
//for(; j>0&&data[j-1]>temp; j--) {
//
//data[j] = data[j-1];
//
//}
//data[j]=temp;
//}
}
//选择排序算法的一般策略：搜索整个值列，以找到最小值。将该值与值列中第一个位置上的值进行交换。
//搜索剩下的值列（第一个除外），以找到其中的最小值，然后将其与值列中第二个位置上的值进行交换。
//对值列中的每个位置重复该过程。在算法结束时，就完成了对值列的排序。
public static void select(int[] data) {
int temp = 0;
int length = data.length;
for(int i=0; i<length; i++) {
int minindex = i;
for(int j=i+1;j<data.length;j++) {
if(data[i]>data[j]) {
minindex = j;
}
}
if(minindex != i) {
temp = data[i];
data[i] = data[minindex];
data[minindex] = temp;
}
}
}
//冒泡排序算法的一般性策略：搜索整个值列，比较相邻元素，
//如果两者的相对次序不对，则交换它们，其结果是最大值“想水泡一样”移动到值列的最后一个位置上,
//这也是它在最终完成排序的值列中合适的位置。
//然后再次搜索值列，将第二大的值移动至倒数第二个位置上，重复该过程，直至将所有元素移动到正确的位置上。
public static void bubble1(int[] data) {
int temp = 0;
int length = data.length;
for(int i=length-1; i>0; i--) {
for(int j=0; j<i; j++) {
if(data[j] > data[j+1]) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
}
public static void bubble2(int[] data) {
int temp = 0;
int length = data.length;
for(int i=0; i<length; i++) {
for(int j=1; j<length-i; j++) {
if(data[j-1] > data[j]) {
temp = data[j-1];
data[j-1] = data[j];
data[j] = temp;
}
}
}
}
//基本思想算法先将要排序的一组数按某个增量dn/2,n为要排序数的个数分成若干组
//每组中记录的下标相差d.对每组中全部元素进行直接插入排序然后再用一个较小的增量d/2对它进行分组
//在每组中再进行直接插入排序。当增量减到1时进行直接插入排序后排序完成。
public static void shell(int[] data) {
double d = data.length;
double length = data.length;
int temp = 0;
while (true) {
d = Math.ceil(d / 2);
int d1 = (int) d;
for (int i = d1; i < length; i++) {
for(int j=i; j<length; j++) {
int k = j;
temp = data[j];
for(; k>=d1&&temp<data[k-d1]; k-=d1) {
data[k] = data[k-d1];
}
data[k] = temp;
}
}
if(d1==1) {
break;
}
}
}
//快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。
//它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
//
//该方法的基本思想是：
//
//1．先从数列中取出一个数作为基准数。
//
//2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
//
//3．再对左右区间重复第二步，直到各区间只有一个数。
//第一次排序a=0，b=data.length-1
public static void quick(int[] data,int a,int b) {
if(a>=b) return;
int key = data[a];
int i = a;
int j = b;
while(j>i) {
for(;j>i;j--) {
if(data[j]<key) {
data[i] = data[j];
i++;
break;
}
}
for(;i<j;i++) {
if(data[i]>key) {
data[j] = data[i];
j--;
break;
}
}
}
data[i] = key;
quick(data,a,i-1);
quick(data,i+1,b);
}
public static void main(String[] args) {
int []array = {4,5,17,23,3,2,6,7,1};
quick(array,0,array.length-1);
for(int j=0; j<array.length; j++) {
System.out.println(array[j]);
}
}
}
