此文章是vip文章,如何查看?  

1,点击链接获取密钥 http://nicethemes.cn/product/view29882.html

2,在下方输入文章查看密钥即可立即查看当前vip文章


java 面试清单 八大排序算法

  • 时间:
  • 浏览:
  • 来源:互联网

01 插入排序–直接插入排序

思路:将待排序的无序数组中的每第一个元素arr[j],插入到前面的有序数组中arr[0]...ar[j-1]
为arr[j]在有序数组中找到对应的插入位置p,那么需要将p...j-1这几个元素都向后移动,为了防止arr[j]的值被覆盖,因此先将arr[j]的值存储起来。
//默认整个数组的第一个元素就是有序数组的第一个元素,因此无序数组从数组的第二个开始
for(int i =1; i<arr.length; i++){
//令j指向当前i的位置,原因是:因为在后移动的时候将j--,如果设置为j=i-1,虽然逻辑上理解起来是这样没错,但是数组的j很可能减少到-1
	int j = i;
	int temp = arr[i];
	while(j>0 && arr[j-1] > arr[i]){
	//使元素往后移动
		arr[j] = arr[j-1];
		j--;
	}
	arr[j] = temp;
}

02 插入排序–希尔排序

public void XierInsertSort(int arr[], int dk){
	for(int i = dk; i<arr.length; i++){
		if(arr[i] < arr[i-dk]){
			int cur = arr[i];
			for(int j=i-dk; j>=0&& cur<arr[i-dk]; j=j-dk){
				arr[j+dk] = arr[j];
			}
			arr[j] = cur;
		}
	}
}
public void XierSort(int arr[]){
	dk = arr.length/2;
	while(dk>=1){
		XierInsertSort(int arr[], dk);
		dk /= 2;
	}
}

03 选择排序—简单选择排序

打擂台法:
//控制擂主需要循环几次
for(int i=0; i<arr.length-1; i++){
	int LeiZhu = i;
	//控制擂主与剩下所有的进行对比
	for(int j=i+1; j<arr.length;i++){
		if(arr[LeiZhu] > arr[j){
		//只需要记录下标,这样可以减少比较赋值的次数,降低复杂度
			LeiZhu = j;
		}
	}
	int temp = arr[LeiZhu];
	arr[LeiZhu] = arr[i];
	arr[i] = temp;
}

04 选择排序—堆排序

05 交换排序—冒泡排序

//外循环控制 总共遍历几次
for(int i=0; i<arr.length-1;i++){
	//内循环控制 一次循环遍历的过程
	for(int j=0; j<arr.length-i-1; j++){
		//每次遍历都是从头开始
		if(a[j]  > a[j+1]){
			temp = a[j];
			a[j] = a[j+1];
			a[j+1] = temp;
			}
	}
}

06 交换排序—快速排序

递归思路:

  1. 选中povit位置的元素,让array[povit]作为分界线,array[povit]右边的元素均大于array[povit]值,左边的元素均大于array[povit]的值
  2. 让povit作为分界线,开始判断从povit开始到数据末尾的快速排序 [array, povit+1, array.length-1]
  3. 让povit作为分界线,开始判断从数据开头到povit的快速排序[array, 0, povit-1];

单个递归内部细节:

  1. 选择一个povit作为基础元素
  2. 令left指向数组的第一个元素, right指向最后一个元素
  3. 从right开始进行判断:
    如果array[right]大于或者等于array[povit]成立: right = right-1;
    否则,right停止,执行步骤d
  4. 从left开始进行判断:
    如果array[left]小于或者等于array[povit]成立: left = left + 1;
    否则,left停止,执行步骤e
  5. 交换array[right]和array[left]两个元素的位置,然后继续执行步骤c
  6. 直至left == right时结束,此时交换array[povit]和array[left]两个元素的位置
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        // 递归结束条件:startIndex大等于endIndex的时候

        if (startIndex >= endIndex) {

            return;

        }

        // 得到基准元素位置

        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素,分成两部分递归排序

        quickSort(arr, startIndex, pivotIndex - 1);

        quickSort(arr, pivotIndex + 1, endIndex);

    }


    private static int partition(int[] arr, int startIndex, int endIndex) {

        // 取第一个位置的元素作为基准元素

        int pivot = arr[startIndex];

        int left = startIndex;

        int right = endIndex;

        while( left != right) {

            //控制right指针比较并左移

            while(left<right && arr[right] > pivot){

                right--;

            }

            //控制right指针比较并右移

            while( left<right && arr[left] <= pivot) {

                left++;

            }

            //交换left和right指向的元素

            if(left<right) {

                int p = arr[left];

                arr[left] = arr[right];

                arr[right] = p;

            }

        }

        //pivot和指针重合点交换

        int p = arr[left];

        arr[left] = arr[startIndex];

        arr[startIndex] = p;

        return left;

    }


    public static void main(String[] args) {

        int[] arr = new int[] {4,7,6,5,3,2,8,1};

        quickSort(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));

    }

07 归并排序

思路:
1 ‘归’: 利用递归的分解数列
2 ‘并’: 合并数列
public void mergearray(int arr[], int left, int mid, int right, int temp[]){
	int i = left; 
	int j = mid+1;
	int k = 0; 
	while(i <= mid && j<=right){
	//两个有序数组进行比较,取小的那个
		if(arr[i] > arr[j]){
			temp[k++] = arr[j++];
		}else{
			temp[k++] = arr[i++];
		}
	//当右边序列走完了,左边剩下全放上去
	while(i<=mid){
		temp[k++] = arr[i++];
	}
	//当左边序列走完了,右边剩下全放上去
	while(j<mid){
		temp[k++] = arr[j++]
	}		
	for(int i=0; i<k; i++){
		arr[first+i] = temp[i];
	}
	}
}
public void mergesort(int arr[], int left, int right, int temp[]){
	if(right>left){
		int mid = (left+right)/2;
		//递归分解左边序列
		mergesort(arr, left, mid, temp)
		//递归分解右边序列
		mergesort(arr, mid+1, right, temp)
		//合并数列
		mergearray(arr, left, mid, right, temp)
	}
}

08 基数排序

在这里插入图片描述

本文链接http://element-ui.cn/news/show-332734.aspx