Demo entry 6763305

田丰瑞

   

Submitted by anonymous on Oct 21, 2018 at 14:47
Language: Java. Code size: 3.2 kB.

import java.util.ArrayList;
import java.util.Collections;
public class sortlist {
	//直接插入排序
	static void insort(ArrayList<Integer> myli) {
		for (int i = 1; i<myli.size(); ++i) {
			for(int j = i; (j>0 )&& ((int)myli.get(j)<(int)myli.get(j-1)); --j) {
				Collections.swap(myli, j, j-1);
				
			}
		}
	}
	//冒泡排序
	static void bubsort(ArrayList<Integer> myli) {
		for (int i = 0; i<myli.size()-1; ++i) {
			for(int j = myli.size()-1; j>i; --j) {
				if ((int)myli.get(j)<(int)myli.get(j-1)) {
					Collections.swap(myli, j, j-1);
				}
			}
		}
	}
	//选择排序
	static void selsort(ArrayList<Integer> myli) {
		for (int i = 0; i<myli.size()-1; ++i) {
			int lowindex = i;
			for (int j = myli.size()-1; j>i; --j) {
				if ((int)myli.get(j) < (int)myli.get(lowindex))
					lowindex = j;
			}
			Collections.swap(myli, i, lowindex);
		}
	}
	
	//快速排序的主干代码
	static void myqsort(ArrayList<Integer> myli, int i, int j) {
		int pivotindex = findpivot(myli,i,j);
		Collections.swap(myli, j, pivotindex);
		int k = partition(myli, i-1, j, (int)myli.get(j));
		Collections.swap(myli, j, k);
		if ((k - i) > 1) myqsort(myli, i, k-1);
		if ((j - k) > 1) myqsort(myli, k+1, j);
	}
	//快速排序将比轴值大或小的放在不同两侧
	private static int partition(ArrayList<Integer> myli, int l, int r, int pivot) {
		//int sl = l+1;
		//int sr = r;
		
		/*
		 System.out.println(pivot);
		 for (int i = sl; i<=sr; ++i) {
			System.out.printf("%d ",myli.get(i));
		}
		System.out.println();
		 */
		do {
			while((int)myli.get(++l) < pivot);
			while(r!=0 && (int)myli.get(--r)> pivot);
			Collections.swap(myli, l, r);
		}while(l<r);
		Collections.swap(myli, l, r);
		/*for (int i = sl; i<=sr; ++i) {
			System.out.printf("%d ",myli.get(i));
		}
		System.out.println();*/
		return l;
	}
	//选择序列的首项,末项和中间项值的中间值作为轴值
	private static int findpivot(ArrayList<Integer> myli, int i, int j) {
		//int min = (int)myli.get(i);
		//int max = (int)myli.get(j);
		int ju = (j-i)/2;
		//int mid = (int)myli.get(ju);
		if((int)myli.get(j) < (int)myli.get(i)) {
			int tem = j;
			j = i;
			i = tem;
		}
		if((int)myli.get(i) > (int)myli.get(ju)) {
			int tem = i;
			i = ju;
			ju = tem;
		}
		if((int)myli.get(j)<(int)myli.get(ju)) {
			int tem = j;
			j = ju;
			ju = tem;
		}
		//System.out.printf("%d %d %d %d %d %d\n",(int)myli.get(j),i,(int)myli.get(i),j,(int)myli.get(ju),ju);
		
		return ju;
	}
	//归并排序
	static void mergesort(ArrayList<Integer> array, ArrayList<Integer> temp, int l, int r) {
		int mid = (l+r)/2;
		if (l == r) return;
		mergesort(array,temp,l,mid);
		mergesort(array,temp,mid+1,r);
		for (int curr = l; curr<r+1; ++curr) {
			temp.set(curr, array.get(curr));
		}
		int i1 = l; int i2 = mid +1;
		for (int curr = l; curr<r+1; ++curr) {
			if (i1 == mid+1) array.set(curr, temp.get(i2++));
			else if (i2>r) array.set(curr, temp.get(i1++));
			else if (temp.get(i1) < temp.get(i2)) array.set(curr, temp.get(i1++));
			else array.set(curr, temp.get(i2++));
		}
		//int tem = 0;
		//for(int i = l; i<r+1; ++i) {
			//array.set(i,temp.get(tem++));
			//System.out.printf("%d ",array.get(i));
		//}
		//System.out.println();
	}
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).