常见排序算法总结-蒲公英云

常见排序算法总结

冒泡排序

/* 重复地走访要排序的元素，一次比较相邻两个元素，如果他们是逆序就把他们调换过来，直到没有元素再需要交换，排序完成。 @param nums */

public static void bubbleSort(int[] nums){ 
    int len = nums.length;
    boolean flag = false;
    for(int i=0;i<len;i++){ 
        flag = false;
        for(int j =1;j<len-i;j++){ 
            if(nums[j-1] > nums[j]){ 
                int tmp = nums[j-1];
                nums[j-1]= nums[j];
                nums[j] = tmp;
            }
        }
        if(flag){ 
            break;
        }
    }
}

选择排序

/* 选择排序类似于冒泡排序，选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的末尾位置，然后再从剩余未排序元素中继续寻找最小（大）元素 放到已排序序列的开始，以此类推，直到所有元素均排序完毕。 @param nums */

public static  void  selectSort(int [] nums){ 
    int len = nums.length;
    int maxIndex=0;
    for(int i=len-1;i>=0;i--){ 
        maxIndex = 0;
        for(int j=0;j<=i;j++){ 
          if(nums[j]>nums[maxIndex]){ 
              maxIndex = j;
          }
        }
        int tmp =  nums[i];
        nums[i] = nums[maxIndex];
        nums[maxIndex] = tmp;
    }
}

插入排序

/* 首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。时间复杂度：O(n^2)，最优时间复杂度：O(n^2),平均时间复杂度：O(n^2) @param nums /

public  static void insertionSort(int [] nums){ 
    int len = nums.length;
    int tmp;
    int j;
    for(int i=1;i<len;i++){ 
        tmp = nums[i];
        for( j=i;j>0 && nums[j-1] > tmp;j--){ 
            nums[j] = nums[j-1];
        }
        nums[j] = tmp;
    }
}

快速排序

/* 从数列中挑出一个元素，称为”基准”（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 @param nums @param l @param r /

public static void quickSort(int[] nums,int l,int r){ 
    if(l<r){ 
        int i,j,x;
        i = l;
        j = r;
        x= nums[i];
        while (i<j){ 
            while (i<j&&nums[j]>x);{ 
                j--;
            }
            if(i<j){ 
                nums[i++] = nums[j];
            }
            while (i<j && nums[i]<x){ 
                i++;
            }
            if(i<j){ 
                nums[j--] = nums[i];
            }
        }
        nums[i] = x;
        quickSort(nums,l,i-1);
        quickSort(nums,i+1,r);
    }
}

堆排序

/* 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算 /
public static void headSort(int[] nums){

    for(int i = nums.length/2;i>=0;i--){ 
        heapAdjust(nums,i,nums.length);
    }
    for(int i=nums.length-1,temp=0;i>0;i--){ 
        temp = nums[i];
        nums[i] = nums[0];
        nums[0] = temp;
        heapAdjust(nums,0,i);
    }
}
private static void heapAdjust(int[] nums, int parent, int len) { 
    int temp = nums[parent];
    int lChild = 2*parent+1;
    while (lChild <len){ 
        if(lChild +1<len && nums[lChild +1 ] > nums[lChild])
        { 
            lChild ++;
        }
        if(nums[parent] > nums[lChild]){ 
            break;
        }
        nums[parent] = nums[lChild];
        parent = lChild;
        lChild = 2*lChild+1;
    }
    nums[parent] = temp;
}