冒泡排序
1,比较相邻的元素,如果第一个比第二个大,就交换位置。
2,对每一个相邻元素做同样的操作,做完这一步之后,最后的元素会是最大的数
3,重复以上步骤,直到没有任何一对数字需要比较
public static void bubbleSort(int [] array){ //第一轮确定最大的数,第二轮确定第二大的数,,依次下去
//3 1 5 8 2 9 4 6 7
for(int i=array.length-1;i>0;i--){
for(int j = 0;j<i;j++){
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
选择排序
1,从未排序序列中,找到值最小的元素
2,如果最小元素不是未排序序列的第一个元素,将其和未排序序列第一个元素互换
3,重复1,2步,直到排序结束
//顺序表的排序 (选择排序法)(试用场景:个位数的排序次数)
public static void selectSort(int [] array){//两个两个比较,,选出最小的,然后拿最小的继续和后面做两两对比
for(int i =0;i<array.length-1;i++){
int index = i;
for(int j = index+1;j<array.length;j++){
if(array[j] <array[index]){
index = j;
}
}
if(index != i){//如果当前就是最小的,就不需要交换
int temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
}
快速排序
1,从数列中挑出一个元素,称为基准。
2,所有比基准值小的元素放在基准值的前面,所有比基准值大的元素放在基准值的后面(相同的数可以到任意一边)。这样操作之后,基准值就处于数列的中间位置。
3,递归调用,把小于基准值的子数列和大于基准值元素的数列排序。一直到子数列的大小是0或者一的时候就排序好了。
/**
* 快速排序 31 21 59 68 12 40 (先取一个数据出来,第一轮排序之后左边都小于这个数,右边都大于这个数,然后一直循环)
*/
public static void quickSort(int [] array,int begin,int end){
if(end-begin<=0) return;
int low = begin;//0
int high = end;//5
int x = array[begin];
//由于会分别从两头取数据
boolean direction = true;
L1:
while(low<high){
if(direction){//从右往左找
for(int i = high;i>low;i--){
if(array[i]<=x){
array[low++] = array[i];
high = i;
direction = !direction;
continue L1;
}
}
high = low;//如果一直上面的if从未进入,让两个指针重合
}else{//从左往右找
for(int i=low;i<high;i++){
if(array[i]>=x){
array[high--]=array[i];
low = i;
direction = !direction;
continue L1;
}
}
low = high;
}
}
array[low] =x;//第一轮确定X位置,左边的都小于X,右边的都大于X
quickSort(array,begin,low-1);
quickSort(array,low+1,end);
}
归并排序
二叉树的后序遍历思想
1,将序列每次折半拆分
2,比较左边和右边值的大小,然后排好序合并。按照二叉树的后序遍历的方式一层层的往上合并
3,递归调用
/**
* 归并排序 思想:二叉树的后序遍历
* @param array
* @param left 0
* @param right 数组长度-1
*/
public static void mergeSort(int[] array,int left,int right){
if(left == right){
return;
}else{
int mid = (left+right)/2;
//左半边往下拆分
mergeSort(array,left,mid);
//右半天边往下拆分
mergeSort(array,mid+1,right);
//排序之后合并
merge(array,left,mid+1,right);
}
}
/**
* 将一个左右两边分别排好序的数组合并成一个完整的排好序的数组
*/
//1,2,5,9 ======== 3,4 ,10 ,11
public static void merge(int []array,int left,int mid ,int right){
//1,将一个数组分成左右两个数组
int leftSize = mid-left;
int rightSize = right - mid + 1;
int [] leftArray = new int[leftSize];
int [] rightArray = new int[rightSize];
//将数组的数填充到左右两个数组中去
for(int i = left;i<mid;i++){
leftArray[i-left] = array[i];
}
for(int i = mid;i<=right;i++){
rightArray[i-mid] =array[i];
}
//将两个数组排序后合并
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k] = leftArray[i];
k++;i++;
}else{
array[k] = rightArray[j];
k++;j++;
}
}
while(i<leftSize){
array[k] = leftArray[i];
k++;i++;
}
while(j<rightSize){
array[k] = rightArray[j];
k++;j++;
}
}
插入排序
1,从第一个元素开始,该元素可以认为已经被排序。
2,取出下一个元素,在已经排序的元素序列中从后向前扫描。
3,如果已排序的元素大于新元素,将该元素移到下一个位置,新元素插入到该元素的位置。
4,重复步骤3,一直找到新元素应该插入到已排序的序列中的位置。保证新插入元素之后该序列还是一个排好序的序列。
5,重复步骤2-5
代码实现
//直接插入排序
public void insertSort(int [] array){
for (int i = 1;i<array.length;i++){
int j = i;
int target = array[j];
while(j>0 && target<array[j-1]){
array[j] = array[j-1];
j--;
}
array[j] = target;
}
}
希尔排序
一种改进的插入排序
将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;再将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成整个排序。
@Test
public void test(){
int[] array=new int[]{2,3,4,5,6,7,1,8,9};
shellSort(array,4);
shellSort(array,2);
shellSort(array,1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
private void shellSort(int[] array, int step) {
for(int k =0;k<step;k++){
//直接插入排序
for(int i = k+step;i<array.length;i=i+step){
int j = i;
int target = array[j];
while(j>step - 1 && target<array[j-step]){
array[j] = array[j - step];
j = j - step;
}
array[j] = target;
}
}
}
堆排序
完全二叉树中任何一个非叶子节点的值均不大于(或不小于)其左,右孩子节点的值。由此可知大顶堆的堆顶的值是所有堆中值最大的,小顶堆则是最小的。所以堆排序的过程就是将待排序的序列构造成一个堆,选出堆顶移走,再把剩余的元素调整成堆,找出最大的再移走,重复直至有序。
void heapSort(int array[]){
//循环一次,获取一次堆顶最大值,循环完毕数据就排好序了
for(int i = array.length-1;i>0;i--){
//建堆
max_heapify(array,i);
//将堆顶最大值存入到数组的最大索引处
int temp = array[0];
array[0] = array[i];
array[i] = temp;
}
}
/**
* 创建一个大顶堆
* @param array
* @param n 数组的长度-1
*/
void max_heapify(int [] array,int n){
int child;
for(int i = (n-1)/2;i>= 0;i--){//非叶子节点
//该非叶子节点的左子节点位置
child = 2*i+1;
//假设该节点的右子节点存在,则比较左右子节点的值的大小,得到其中的大的值
if (child != n && array[child] < array[child + 1]) {
child++;
}
//交换父节点与左右子节点中的最大值
if (array[i] < array[child]) {
int temp = array[i];
array[i] = array[child];
array[child] = temp;
}
}
}
基数排序
将所有待比较数值统一为同样的数位长度,数位较短的数前面补零,然后从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序数列。
public static void sort(int[] arr) {
if (arr.length <= 1) return;
//取得数组中的最大数,并取得位数
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int maxDigit = 1;
while (max / 10 > 0) {
maxDigit++;
max = max / 10;
}
//申请一个桶空间
int[][] buckets = new int[10][arr.length];
int base = 10;
//从低位到高位,对每一位遍历,将所有元素分配到桶中
for (int i = 0; i < maxDigit; i++) {
int[] bktLen = new int[10]; //存储各个桶中存储元素的数量
//分配:将所有元素分配到桶中
for (int j = 0; j < arr.length; j++) {
int whichBucket = (arr[j] % base) / (base / 10);
buckets[whichBucket][bktLen[whichBucket]] = arr[j];
bktLen[whichBucket]++;
}
//收集:将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
int k = 0;
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktLen[b]; p++) {
arr[k++] = buckets[b][p];
}
}
System.out.println("Sorting: " + Arrays.toString(arr));
base *= 10;
}
}
各种排序性能对比如下:

网友评论