生活中常用的排序算法:冒泡排序、插入排序、快速排序
- package com.tao.bao;
- /**
- * @author Administrator
- *
- */
- public class SortAll {
- /**
- * @param args
- * 插入排序
- */
- public int[] insertionSort(int[] arr){
- int j;
- for(int p=1;p<arr.length;p++){
- int tmp=arr[p];
- for(j=p;j>0&&arr[j-1]>tmp;j--)
- {
- arr[j]=arr[j-1];
- }
- arr[j]=tmp;
- }
- return arr;
- }
- /**
- * ,冒泡排序
- * @param arr
- * @return
- */
- public int[] maoPaoSort(int[] arr){
- for(int i=0;i<arr.length;i++){
- for(int j=0;j<arr.length-i-1;j++){
- if(arr[j]>arr[j+1])
- {
- int tmp = arr[j];
- arr[j]=arr[j+1];
- arr[j+1]=tmp;
- }
- }
- }
- return arr;
- }
- /*
- * 快速排序
- */
- public int partition(int[] arr,int left,int right){
- int x = arr[right]; //选取最后一个元素为主元,算法导论中算法
- int i = left-1;
- for(int j=left;j<right;j++){
- if(arr[j]<=x){
- i=i+1;
- swap(arr,i,j);
- }
- }
- swap(arr,i+1, right);
- return i+1;
- }
- public int[] quicksort(int[] arr,int left,int right){
- if(left<right){
- int q = partition(arr, left, right);//关键
- quicksort(arr, left, q-1);
- quicksort(arr, q+1, right);
- return arr;
- }
- return null;
- }
- public static void swap(int arr[],int a,int b){
- int temp = 0;
- temp = arr[a];
- arr[a] =arr[b];
- arr[b] = temp;
- }
- public static void main(String[] args) {
- SortAll all = new SortAll();
- int arr[] = {2,8,7,1,3,5,6,4};
- int newarr1[] = all.insertionSort(arr);
- System.out.println("insertionSort方法");
- for(int i=0;i<newarr1.length;i++){
- System.out.print(newarr1[i]+" ");
- }
- System.out.println();
- int newarr[] = all.maoPaoSort(arr);
- System.out.println("maoPaoSort方法");
- for(int i=0;i<newarr.length;i++){
- System.out.print(newarr[i]+" ");
- }
- System.out.println();
- int arrquick[] = all.quicksort(arr, 0, arr.length-1);
- System.out.println("arrquick方法");
- for(int i=0;i<arrquick.length;i++){
- System.out.print(arrquick[i]+" ");
- }
- System.out.println();
- }
- }