数据结构课程设计之java排序.doc

《数据结构课程设计》

专业:计算机科学与技术
姓名：周兵
学号:

一、 需求分析

一、设计代码：
1. 直接插入排序：
public class InsertSort {
public static <T extends Comparable<? super T>> void insertSort(T[] array) {
for (int i = 1; i <= array.length - 1; i++) {
int j = i;
while (j>=1 && array[j].compareTo(array[j - 1]) < 0) {
T temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;

j--;
}
}
}

public static void main(String[] args) {
Integer[] testArray = {23, 25, 12, 42, 35,33,43,57};
System.out.println("排序前 :");
for (Integer item : testArray) {
System.out.print(item);
System.out.print(' ');
}
System.out.println();
System.out.println("-------------------");
InsertSort.insertSort(testArray);
System.out.println("排序后 :");
for (Integer item : testArray) {
System.out.print(item);
System.out.print(' ');
}
}
}
实验结果：

2. 折半插入排序：
public class BInsertSort {

public static void bInsertSort(int[] temp) {
int length = temp.length;
for (int i = 1; i < length; i++) {
int tempVal = temp[i];
int low = 0;
int high = i - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (tempVal < temp[middle])
high = middle - 1;
else
low = middle + 1;
}
for (int j = i; j > high + 1; j--)
temp[j] = temp[j - 1];
temp[high + 1] = tempVal;
}
}

public static void main(String[] args) {
int[] a = { 5, 1, 76, 2, 4, 84, 36, 22, 62, 90 };
bInsertSort(a);
System.out.println("排序后:");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
}
}
实验结果：

3. 希尔排序:
public class InsertionSort {

public void shellInertionSort(double [] sorted, int inc){
int sortedLen= sorted.length;
for(int j=inc+1;j<sortedLen;j++ ){
if(sorted[j]<sorted[j-inc]){
sorted[0]= sorted[j];//先保存一下后面的那个
int insertPos=j;
for(int k=j-inc;k>=0;k-=inc){
if(sorted[k]>sorted[0]){
sorted[k+inc]=sorted[k];
if(k-inc<=0){
insertPos = k;
}
}else{
insertPos=k+inc;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}

public void shellInsertionSort(double [] sorted){

int[] incs={7,5,3,1};
int num= incs.length;
int inc=0;
for(int j=0;j<num;j++){
inc= incs[j];
shellInertionSort(sorted,inc);
}
}

public static void main(String[] args) {

Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;j<arraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
InsertionSort sorter=new InsertionSort();
sorter.shellInsertionSort(sorted);
System.out.print("After Sort:");
for(int j=1;j<sorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
实验结果：

4. 冒泡排序：
public class BubbluSort {

public static void sortiere(int[] x) {
boolean unsortiert = true;
int temp;
while (unsortiert) {
unsortiert = false;
for (int i = 0; i < x.length - 1; i++)
if (x[i] > x[i + 1]) {
temp = x[i];
x[i] = x[i + 1];
x[i + 1] = temp;
unsortiert = true;
}
}
}

public static void main(String[] args) {
int[] liste = { 0, 9, 4, 6, 2, 8, 5, 1, 7, 3 };
System.out.println("排序前：");
for (int i = 0; i < liste.length; i++)
System.out.print(liste[i] + " ");
System.out.println();
System.out.println("-----------------------------");
System.out.println("排序后：");
sortiere(liste);
for (int i = 0; i < liste.length; i++)
System.out.print(liste[i] + " ");
}
}
实验结果：

5. 快速排序：
public class ExchangeSort {

public void QuickExchangeSortBackTrack(double[] sorted,
int low, int high) {
if (low < high) {
int pivot = findPivot(sorted, low, high);
QuickExchangeSortBackTrack(sorted, low, pivot - 1);
QuickExchangeSortBackTrack(sorted, pivot + 1, high);
}
}

public int findPivot(double[] sorted, int low, int high) {
sorted[0] = sorted[low];
while (low < high) {
while (low < high && sorted[high] >= sorted[0])
--high;
sorted[low] = sorted[high];
while (low < high && sorted[low] <= sorted[0])
++low;
sorted[high] = sorted[low];
}
sorted[low] = sorted[0];
return low;
}

public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.println("排序前:");
for (int j = 1; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
System.out.println("------------------------------");
ExchangeSort sorter = new ExchangeSort();
sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize - 1);
System.out.println("排序后:");
for (int j = 1; j < sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
实验结果：

6. 直接选择排序：
public class SelectionSort {

public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;j<sortedLen;j++){
int jMin= getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}

public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}

public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;
int minJ=1;
double min= Double.MAX_VALUE;
for(int j=i;j<sortedLen;j++){
if(sorted[j]<min){
min= sorted[j];
minJ= j;
}
}
return minJ;
}

public static void main(String [] args){
Random random= new Random(6);
int arraysize=9;
double [] sorted=new double[arraysize];
System.out.println("排序前:");
for(int j=1;j<arraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
System.out.println("------------------------");
SelectionSort sorter=new SelectionSort();
sorter.straitSelectionSort(sorted);
System.out.println("排序后:");
for(int j=1;j<sorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}

实验结果：

7. 堆排序：
public class SelectionSort {

public void heapAdjust(double [] sorted,int start,int end){
if(start<end){
double temp= sorted[start];
for(int j=2*start;j<end;j *=2){
if(j+1<end && sorted[j]-sorted[j+1]>10e-6){
++j;
}
if(temp<=sorted[j]){
break;
}
sorted[start]=sorted[j];
start=j;
}
sorted[start]=temp;
}
}

public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(i<sortedLen && j<sortedLen && i<j && i>=0 && j>=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}

public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;
for(int i=sortedLen/2;i>0;i--){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i>1;--i){
exchange(sorted,1,i);
heapAdjust(sorted,1,i-1);
}
}

public static void main(String [] args){
Random random= new Random(6);
int arraysize=10;
double [] sorted=new double[arraysize];
System.out.println("排序前:");
for(int j=1;j<arraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
System.out.println("------------------------");
SelectionSort sorter=new SelectionSort();
sorter.heapSelectionSort(sorted);
System.out.println("排序后:");
for(int j=1;j<sorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
实验结果：

8. 归并排序:
public class MergeSort {

private double[] bridge;//辅助数组

public void sort(double[] obj){
if (obj == null){
throw new NullPointerException("The param can not be null!");
}
bridge = new double[obj.length]; // 初始化中间数组
mergeSort(obj, 0, obj.length - 1); // 归并排序
bridge = null;
}
private void mergeSort(double[] obj, int left, int right){
if (left < right){
int center = (left + right) / 2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}

private void merge(double[] obj, int left, int center, int right){
int mid = center + 1;
int third = left;
int tmp = left;
while (left <= center && mid <= right){
if (obj[left]-obj[mid]<=10e-6){
bridge[third++] = obj[left++];
} else{
bridge[third++] = obj[mid++];
}
}
while (mid <= right){
bridge[third++] = obj[mid++];
}
while (left <= center){
bridge[third++] = obj[left++];
}
// 将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}

private void copy(double[] obj, int left, int right){
while (left <= right){
obj[left] = bridge[left];
left++;
}
}

public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.println("排序前:");
for (int j = 0; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
System.out.println("--------------------------");
MergeSort sorter = new MergeSort();
sorter.sort(sorted);
System.out.println("排序后:");
for (int j = 0; j < sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
实验结果：

9. 基数排序：
public class RadixSort {

private int keyNum=-1;
private Vector<Vector<Double>> util;

public void distribute(double [] sorted, int nth){
if(nth<=keyNum && nth>0){
util=new Vector<Vector<Double>>();
for(int j=0;j<10;j++){
Vector <Double> temp= new Vector <Double>();
util.add(temp);
}
for(int j=0;j<sorted.length;j++){
int index= getNthDigit(sorted[j],nth);
util.get(index).add(sorted[j]);
}
}
}

public int getNthDigit(double num,int nth){
String nn= Integer.toString((int)num);
int len= nn.length();
if(len>=nth){
return Character.getNumericValue(nn.charAt(len-nth));
}else{
return 0;
}
}

public void collect(double [] sorted){
int k=0;
for(int j=0;j<10;j++){
int len= util.get(j).size();
if(len>0){
for(int i=0;i<len;i++){
sorted[k++]= util.get(j).get(i);
}
}
}
util=null;
}

public int getKeyNum(double [] sorted){
double max= Double.MIN_VALUE;
for(int j=0;j<sorted.length;j++){
if(sorted[j]>max){
max= sorted[j];
}
}
return Integer.toString((int)max).length();
}

public void radixSort(double [] sorted){
if(keyNum==-1){
keyNum= getKeyNum(sorted);
}
for(int i=1;i<=keyNum;i++){
distribute(sorted,i);
collect(sorted);
}
}

public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.println("排序前:");
for (int j = 0; j < arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
System.out.println("--------------------------------");
RadixSort sorter = new RadixSort();
sorter.radixSort(sorted);
System.out.println("排序后:");
for (int j = 0; j < sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
实验结果：

二、课程设计总结
通过这次课程设计，加深了我对《数据结构》这门功课的结识，更加加深了我对程序算法的理解。我觉得课程设计这种形式是我们真正需要的，可以让我们学到很多，涉及书上的、书外的。而有一句话给我的体会是最深的，就是 理论！=实际。在学排序算法的时候，读了书上的算法描述，觉得自己都会了，考试的题目也做出来了，但真的到编程去实现的时候，却不是一次就能成功的，总会出点差错，等到程序终于能运营的时候，才真正体会到这些算法的精髓。理论和实际永远相差那么一点，不去实现是体会不出来的。
在这里，当然还要感谢知道指导老师的辛勤教导，让我对《数据结构》有了更深的体会和理解，让我知道了怎么在实践中去应用算法，算法给程序带来的好处与效率等等。再次感谢老师的教导！