编程有很多排序方法,我总结了一些排序方法,欢迎大家补充。java有选择排序、冒泡排序、快速排序、插入排序、希尔排序。
选择排序:头角标与后面每个元素比较,如果符合条件换位。
public static void selectSort(int[] arr){
for(int x=0;x<arr.length-1;x++){
for(int y=x+1;y<arr.length;y++){
if(arr[x]>arr[y]){
int tmp=arr[x];
arr[x]=arr[y];
arr[y]=tmp;
}
}
}
}
冒泡排序:相邻的两个元素进行比较,如果符合条件换位
public static void bubbleSort(int[] arr){
for(int x=0;x<arr.length-1;x++){
for(int y=0;y<arr.length-x-1;y++){ //减x的原因是每次y比较次数在减少
if(arr[y]>arr[y+1]){
int tmp=arr[y];
arr[y]=arr[y+1];
arr[y+1]=tmp;
}
}
}
}
快速排序:先选择一个值(本例选的是中间值),并依次找出左边比中间值大的与右边比中间值小的,并进行对调,每一轮两边同时进行,直到角标交错时停止,并用递归的形式一直调用函数,直到结束。
public void quickSort(String[] strDate,int left,int right){
String middle,tempDate;
int i,j;
i=left;
j=right;
middle=strDate[(i+j)/2];
do{
while(strDate.compareTo(middle)<0&& i<right)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>left)
j--; //找出右边比中间值小的数
if(i<=j){ //将左边大的数和右边小的数进行替换
tempDate=strDate;
strDate=strDate[j];
strDate[j]=tempDate;
i++;
j--;
}
}while(i<=j); //当两者交错时停止
if(i<right){
quickSort(strDate,i,right);
}
if(j>left){
quickSort(strDate,left,j);
}
}
插入排序:包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。
直接插入排序:无序插有序,将数组中每个数依次插入已经排列好顺序的数组中,需要用到嵌套循环,外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
public static void inSort(int[] arr) {
int num=arr.length;
int i,j;
for(i=0;i<num;i++){
int temp=arr;
for(j=i; j>0 && temp<arr[j-1]; j--){
arr[j]=arr[j-1];
}
arr[j]=temp;
}
}
希尔排序:属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。(下面希尔排序代码还需优化,只能表达思想,还不能正确运行)
public class Test {
public static int[] a = { 10,32, 1, 9, 5, 7, 12, 0, 4, 3 };
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index){
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = (int)DataLength/2; // 计算下次分割的间隔长度
}
}
}
Java的util包中提供了一个数组排序方法,开发时使用该句代码
Arrays.sort(arr); |