用JAVA面向对象方法进行程序设计

Question

已知一个整形数组，长度为10，请随机赋值（范围1-54），然后写出使用快速排序算法对他进行排序的程序。

Answer 1

public class QuickSort {

private int[] data;

QuickSort(int[] data) {
this.data = data;
}

public void quickSort() {
recQuickSort(data, 0, data.length - 1);
}

private void recQuickSort(int[] data, int low, int high) {
// 设置两个滑标
int lowCursor = low + 1;
int highCursor = high;

// 交换时的临时变量
int temp = 0;
// 比较枢值,设为数组的第一个值
int medi = data[low];

while (true) {
// 从低端开始查找，确定大于数 data[low] 所在的位置
while (lowCursor < high && data[lowCursor] < medi) {
lowCursor++;
}

// 从高端开始查找，确定小于数 data[low] 所在的位置。这里要使用 >= 判断确定小于值
while (highCursor > low && data[highCursor] >= medi) {
highCursor--;
}

// 两游标位置出现越界，退出循环
if (lowCursor >= highCursor) {
break;
}

// 交换 data[highCursor] 和 data[lowCursor] 位置数据
temp = data[highCursor];
data[highCursor] = data[lowCursor];
data[lowCursor] = temp;
}

// 由 while 循环退出条件可知：lowCursor > highCursor
// 当前 lowCursor 指向右侧大于 data[low]的第一个位置;
// 而 highCursor 指向左侧小于 data[low]的第一个位置，所以需要交换 data[low] 和
// data[highCursor]的值
data[low] = data[highCursor];
data[highCursor] = medi;

// 递归运算左半部分
if (low < highCursor) {
recQuickSort(data, low, highCursor);
}

// 递归运算右半部分
if (lowCursor < high) {
recQuickSort(data, lowCursor, high);
}
}

//打印数组
public void display() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}

//产生一个包含size个随机数的数组
public static int[] getData(int size){
int data[]=new int[size];
for (int i = 0; i < data.length; i++) {
data[i]=(int)(1+Math.random()*54);//产生一个1-54的随机数,Math.random()是产生0-1的数.
}
return data;
}

//测试
public static void main(String[] args) {
int data[]=getData(10);
QuickSort sort = new QuickSort(data);
sort.display();
sort.quickSort();
sort.display();
}
}

Answer 2

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class ArraySort {

public static void main(String[] args) {
int[] arr = new int[10];
ArrayList arrs = new ArrayList();
Random r = new Random();

System.out.print("排序前10个数分别为:");
for (int i = 0; i < 10; i++) {
arr[i] = r.nextInt(55) + 1;// 初始化10个数.
System.out.print(arr[i] + ",");
arrs.add(arr[i]);
}

Collections.sort(arrs); // 按升序排数
System.out.println("");
System.out.print("排序后10个数分别为:");
for (int i = 0; i < 10; i++) {
System.out.print(arrs.get(i) + ",");

}

}

}

Answer 3

package sort;
public class Sort2 {
public static void main(String args[]) {
int vec[] = new int[10] ;
for(int i=0;i<10;i++){
vec[i]=Math.radom()*54;
}
Sort2 s = new Sort2(); // 实例化对象
s.quicksort(vec, 0, vec.length -1); // 传参并调用quicksort
for (int i=0;i<=vec.length-1;i++) { // 由小到大输出
System.out.println(vec[i]);
}
}
public void swap(int a[], int i, int j) { // 通过临时变量,交换数据
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} // 第一次交换分析
public void quicksort(int a[], int low, int high) { // 假设传入low=0; high=a.length-1;
if (low < high) { // 条件判断
int pivot, p_pos, i; // 声明变量
p_pos = low; // p_pos指向low,即位索引为0位置 ;
pivot = a[p_pos]; // 将0位置上的数值赋给pivot;
for (i = low + 1; i <= high; i++) { // 循环次数, i=1;
if (a[i]>pivot) { // 1位置的数与0位置数作比较: a[1]>a[0]
p_pos++; // 2位与1位比较,3位与2位比较......
swap(a, p_pos, i); // 传参并调用swap
}
}
swap(a, low, p_pos); // 将p_pos设为high再次调用swap
quicksort(a, low, p_pos - 1); // 递归调用,排序左半区
quicksort(a, p_pos + 1, high); // 递归调用,排序右半区
}
}
}