设计一个快速排序的算法：对"12,34,16,24,8,21,26,11,29,16"排序。
* 思路分析：
* 1、首先选定一个元素作为参数，保证该参数位于数组的中间，比该参数大的位于该参数所在
* 数组位置的右边，比该参数小的位于该参数所在数组位置的左边。
*
* 2、位于该参数左边的数组递归调用上述方法，直至数组有序。该参数右边的数组同理。
*
* @author admin
*
*/
public class Quicksor{
/**
* @param args
*/
public static void main(String[] args) {
//arr表示我们要排序的数组了
int[] arr={12,34,16,24,8,21,26,11,29,16};
//输出未排序前的数组，与排序后的数组作比较
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
//设置连个变量当作指针分别指向数组arr[0]元素的下标和arr[arr.length-1]元素的下标
int left=0,right=arr.length-1;
//调用quickSor()函数使数组有序
quickSor(arr,left,right);
//输出排序后的数组，检测我们的成果
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
private static void quickSor(int[] arr, int left, int right) {
//递归调用应满足数组下标left的值小于right
if(left<right){
//获取参数数组元素在有序数组中的位置
int q=sorNum(arr,left,right);
//递归调用quickSor()函数保证数组有序
quickSor(arr,left,q-1);
quickSor(arr,q+1,right);
}
}
//获取参数数组元素在有序数组中的位置的函数
public static int sorNum(int[] arr,int left,int right){
//定义canshu变量并赋值位arr[left]
int canshu=arr[left];
//循环调用的条件：左指针对应元素的下标应小于右指针对应元素的下标
while(left<right){
/**
* 在满足函数条件的情况下，如果参数大于右指针所对应的元素，右指针对应元素的下标减一
* 并将右指针对应的元素赋值给左指针
*/
while(left<right&&canshu<=arr[right]) --right;
arr[left]=arr[right];
/**
* 在满足函数条件的情况下，如果参数大于左指针所对应的元素，左指针对应元素的下标加一
* 并将左指针对应的元素赋值给右指针
*/
while(left<right&&canshu>=arr[left]) ++left;
arr[right]=arr[left];
}
//当跳出while循环时，此时左右指针同时指向同一元素。并把参数赋值给此元素
arr[left]=canshu;
return left;
}
}
|
|
收藏
淘帖
踩
