数据结构课程设计-排序

r[i]=r[j]; i++; }

while(i0){ i++; }

if(i

r[j]=r[i]; j--; } }

r[i]=pivot; return i; }

public void qSort(int low,int high){ if(low

int pivotloc=partition(low,high); qSort(low,pivotloc-1); qSort(pivotloc+1,high); } }

public void quickSort(){ qSort(0,this.curlen-1); }

//简单选择排序算法

public void selectSort() { RecordNode temp;

for (int i = 0; i < this.curlen - 1; i++) { int min = i;

for (int j = i + 1; j < this.curlen; j++) { cm[2].setCpn(cm[2].getCpn()+1);

if (r[j].getKey().compareTo(r[min].getKey()) < 0) { min = j; } }

if (min != i) { temp = r[i]; r[i] = r[min]; r[min] = temp;

cm[2].setMvn(cm[2].getMvn()+3); } } }

//堆排序算法

public void sift(int low, int high){ int i=low; int j=2*i+1;

RecordNode temp=r[i]; while(j

if(j0){ j++; }

if(temp.getKey().compareTo(r[j].getKey())>0){ r[i]=r[j]; i=j;

j=2*i+1; } else{

j=high+1; } }

r[i]=temp; }

public void heapSort(){ int n=this.curlen; RecordNode temp;

for(int i=n/2-1;i>=0;i--){ sift(i,n); }

for(int i= n-1;i>0;i--){ temp=r[0]; r[0]=r[i]; r[i]=temp; sift(0,i); } }

//归并排序算法

public void merge(RecordNode[] r,RecordNode[] order,int h,int m,int t){ int i=h,j=m+1,k=h; while(i<=m&&j<=t){

if(r[i].getKey().compareTo(r[j].getKey())<=0){ order[k++]=r[i++]; } else{

order[k++]=r[j++]; } }

while(i<=m){

order[k++]=r[i++]; }

while(j<=t){

order[k++]=r[j++]; } }

public void mergepass(RecordNode[] r,RecordNode[] order,int s,int n){ int p=0;

while(p+2*s-1<=n-1){

merge(r, order, p, p+s-1, p+2*s-1); p+=2*s; }

if(p+s-1

merge(r, order, p, p+s-1, n-1); } else{

for(int i=p;i<=n-1;i++){ order[i]=r[i]; } } }

public void mergeSort(){ int s=1;

int n=this.curlen;

RecordNode[] temp= new RecordNode[n]; while(s

mergepass(r,temp,s,n); display(); s*=2;

mergepass(temp,r,s,n); display(); s*=2; } } }

//测试类

public class KCSJ_Sort_1 { static SeqList ST = null;

public static void createSearchList() throws Exception { ST=new SeqList(20);

Scanner sc=new Scanner(System.in);

System.out.print(\请输入排序表的表长:\ int n=sc.nextInt();

KeyType[] k= new KeyType[n];

System.out.print(\请输入排序表中的关键字序列:\ for (int i = 0; i < n; i++) { //输入关键字序列 k[i] = new KeyType(sc.nextInt()); }

for(int i=0;i

public static void main(String[] args) throws Exception{ Scanner sc=new Scanner(System.in); //System.out.println(\创建顺序查找表\ //createSearchList(); while(true){

System.out.println(\ *************** 欢迎进入排序系统 ***************\\n \

System.out.println(\ ★ 1 直接插入排序 2.冒泡排序 3.快速排序 ★\\n \

System.out.println(\ ★ 4.直接选择排序 5 堆排序 6.归并排序 ★\\n \

System.out.println (\ ★ 0.退出 ★\\n \

System.out.println(\

*********************************************** \\n \ System.out.print(\请输入选择(0-6):\ int i=sc.nextInt(); switch(i){

case 1: System.out.println(\不带监视哨直接插入排序---\ System.out.println(\创建顺序排序表\ createSearchList(); ST.insertSort();

System.out.print(\排序结果:\ ST.display();

System.out.println(\比较次数为:\ System.out.println(\移动次数为:\

break;

case 2: System.out.println(\冒泡排序---\ System.out.println(\创建顺序排序表\ createSearchList(); ST.bubbleSort();

System.out.print(\排序结果:\ ST.display();

System.out.println(\比较次数为:\