px.java

排序的问题 三种排序算法

public class px
{
		public static void DisArr(int arr[], int arrlen)
		{
		 for (int i=0; i<arrlen; i++)
		 {
		    System.out.print(arr[i]+" ");
		 }
		 System.out.print("\n");
		}


		/*冒泡排序的基本思想是相邻两个元素进行比较，然后交换*/
		/*第一趟后最后一个数组元素是最大或最小元素，然后对前n-1个数重复如此n-1趟*/

		public static void BubbleSort(int arr[], int arrlen)
		{
		 for (int i=0; i<arrlen-1; i++)
		 {
		  for (int j=0; j<arrlen-1-i; j++)
		  {
		   if (arr[j] > arr[j+1])
		   {
			 int tmp;
			 tmp = arr[j];
			 arr[j] = arr[j+1];
			 arr[j+1] = tmp;
		   }      
		  }
		 }
		}

		/*选择排序的基本思想是每一躺挑选出当前比较的数组元素中最大或最小元素，
		与数组的当前比较的数组元素的第一个元素进行交换*/

		public static void SelectSort(int arr[], int arrlen)
		{
		 for (int i=0; i<arrlen-1; i++)
		 {
		 int MinItem = arr[i];
		  int iMin = i;
		  for (int j = i+1; j<arrlen; j++) //每一趟找出最小的数组元素
		  {
		   if (MinItem > arr[j])
		   {
			MinItem = arr[j];
			iMin = j;
		   }
		  }
		  if (iMin != i)
		  {
		   int tmp;
		   tmp = arr[iMin];
		   arr[iMin] = arr[i];
		   arr[i] = tmp;
		  }

		 }
		}


		/*快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序
		的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数
		据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可
		以递归进行，以此达到整个数据变成有序序列。*/
		public static int QuickSort_Partition(int arr[], int iLow, int iHigh)
		{
		 int tmp = arr[iLow];
		 int PivotItem = arr[iLow];
		 while (iLow <iHigh)
		 {
		  while (iLow < iHigh && arr[iHigh] >= PivotItem)
		  {
		   iHigh--;
		  }          
		  arr[iLow] = arr[iHigh];
		  while (iLow < iHigh && arr[iLow] <= PivotItem)
		  {
		   iLow++;
		  }
		  arr[iHigh] = arr[iLow];
		 }
		 arr[iLow] = tmp;
		 return iLow;
		}

		public static void QuickSort(int arr[], int iLow, int iHigh)
		{
		 if (iLow < iHigh)
		 {
		  int iPivotLoc = QuickSort_Partition(arr, iLow, iHigh);
		  QuickSort(arr, iLow, iPivotLoc-1);
		  QuickSort(arr, iPivotLoc+1, iHigh);
		 }
		}


		public static void main(String[] args)
		{
		 int ArrBubble[] = {11,9,29,77,11,89,2,10,5,65};
    	 DisArr(ArrBubble, 10);
		 BubbleSort(ArrBubble, 10);
		 System.out.println("冒泡排序:");
		 DisArr(ArrBubble, 10);

		 int ArrSelect[] = {11,9,29,77,11,89,2,10,5,65};

		 SelectSort(ArrSelect, 10);
		 System.out.println( "选择排序:");
		 DisArr(ArrSelect, 10);

		 int ArrQuick[] = {11,9,29,77,11,89,2,10,5,65};

		 QuickSort(ArrQuick, 0, 9);
		 System.out.println( "快速排序:");
		 DisArr(ArrQuick, 10);
		}

}