java测试开发面试题总结--排序算法_java开发者测试基础题排序

排序算法

稳定性的理解：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，经过排序，这些记录的相对次序保持不变。

不稳定：快速排序，选择排序，希尔排序，堆排序

冒泡排序

public static int[] bubble(int[] arr) {
    	int len = arr.length;
    	int temp = 0;
    	for(int i=0;i<len-1;i++) {
    		for(int j=0;j<len-i-1;j++) {
    			if(arr[j]>arr[j+1]) {
    			     //交换
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    			}
    		}
    	}
    	return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

快速排序

注意：调用快排时【arr.length-1】

quicksort(arr,0,arr.length-1)

quicksort(arr,0,arr.length-1)

public static void quicksort(int[] arr,int left,int right) {
    	if(left>=right)return;
    	
    	int i = left;
    	int j = right;
    	int index = arr[left];
    	int t;

    	while(i<j) {
    		while(arr[j] >= index && i < j) {
    			j--;
    		}
    		while(arr[i] <= index && i < j) {
    			i++;
    		}
    		if(i<j) {
    			t = arr[i];
    			arr[i] = arr[j];
    			arr[j] = t;
    		}
    	}
    	arr[left] = arr[j];
    	arr[j] = index;
    	quicksort(arr,left,j-1);
    	quicksort(arr,j+1,right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

选择排序

    public static void selectSort(int[] arr) {
    	int min = 0;
    	int temp = 0;
    	for(int i=0;i<arr.length;i++) {
    		min = i;
    		for(int j=i+1;j<arr.length;j++) {
    			if(arr[min]>arr[j]) {
    				min = j;
    			}
    		}
    		if(i!=min) {
    			temp = arr[min];
        		arr[min] = arr[i];
        		arr[i] = temp;
    		}
    	}
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

插入排序

    public static void insertSort(int[] arr) {
    	for(int i=1;i<arr.length;i++) {
    		int target = arr[i];
    		int j = i-1;
    		while(j>=0&& arr[j] > target) {
    			arr[j+1] = arr[j];
    			j--;
    		}
    		arr[j+1] = target;
    	}
    }
1
2
3
4
5
6
7
8
9
10
11