本帖最后由 棉/mg花/x糖 于 2013-5-26 18:44 编辑
数据结构：用数组实现快速排序算法（已优化）
注意：算法优化不是很理想，希望哪位大神能继续帮着优化！！谢谢^_^
程序源码如下：- package com.yb.ArrayAndString;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- public class QuickSort {
- static int count = 0;
- int partition(int arr[],int i,int j) { //划分区间
- int temp = arr[i];
- while(i < j) {
- while(i<j && arr[j]>temp) j--; //从第j所指位置起向前搜索
- if(i < j) {
- arr[i] = arr[j];
- i++;
- }
- while(i<j && arr[i]<temp) i++; //从第i所指位置起向后搜索
- if(i < j) {
- arr[j] = arr[i];
- j--;
- }
- }
- arr[i] = temp;
- return i;
- }
- void quickSort(int arr[],int low,int high) { //快速排序方法
- int p;
- if(low < high) {
- p = partition(arr,low,high); //做一次划分排序
- quickSort(arr,low,p-1); //左区间递归
- quickSort(arr,p+1,high); //右区间递归
- count++;
- }
- }
- public static void main(String[] args) throws IOException {
- // TODO Auto-generated method stub
- BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));
- String ch;
- int arr[] = new int[8];
- int len = arr.length;
- System.out.println("请从键盘输入8个整数，一行只输入一个数：");
- for(int i = 0; i < len; i++) {
- ch = keyin.readLine(); //用于读取一个字符串
- arr[i] = Integer.parseInt(ch); //将字符串类型ch转换成整数类型
- }
- //打印原始数据
- System.out.println("原始数据：");
- for(int i = 0; i < len; i++) {
- System.out.print(" "+arr[i]);
- }
- System.out.println("\n");
- QuickSort p = new QuickSort();
- p.quickSort(arr,0,len-1);
- //打印排序结果
- System.out.println("快速排序法的结果：");
- for(int i = 0; i < len; i++) {
- System.out.print(" "+arr[i]);
- }
- System.out.println("\n");
- System.out.println("排序趟数："+count);
- }
- }
|
收藏
淘帖
踩
