排序和搜索算法总结

╰+攻爆jí腚メ 2022-07-15 14:53 131阅读 0赞

# 排序算法 #

--------------------

##  O ( n 2 ) O(n^2) O(n2) 算法 ##

### Bubble Sort ###

*  原理
    
     *  两层循环，内循环对比每一个元素及其右边的元素并将较大的元素swap到右边，在内循环结束后，当前最大的元素将会被移动到其正确的位置上。外层循环控制检查的次数，最多检查length-1次。
     *  在执行算法的过程中，数组分为两部分，左半部分是未排序的，右半部分是排好序的。
 *  时间复杂度： O ( n 2 ) O(n^2) O(n2)。执行 O ( n 2 ) / 2 O(n^2) / 2 O(n2)/2次比较， O ( n 2 ) / 4 O(n^2) / 4 O(n2)/4次swap。原因是每次需要比较的元素都比上次少一个，因为当前最大元素已经被移动到正确位置上，所以共有 n + ( n − 1 ) + ( n − 2 ) + . . . + 1 n + (n - 1) + (n - 2) + ... + 1 n\+(n−1)\+(n−2)\+...\+1次比较，既 O ( n 2 ) / 2 O(n^2) / 2 O(n2)/2次比较。而每次比较移动两个元素，所以共有 O ( n 2 ) / 4 O(n^2) / 4 O(n2)/4次swap。
 *  最坏的情况出现在数组倒叙排列的情况下，在这种情况下每个元素都需要被移动。

代码如下：

public int[] bubbleSort(int[] nums) {
        
    	if (nums == null || nums.length <= 0) {
        
    		return nums;
    	}
    
    	int len = nums.length;
    	for (int i = 0; i < len - 1; i++) {
        
    		boolean swapped = false;
    		for (int j = 0; j < len - 1 - i; j++) {
        
    			if (nums[j] > nums[j + 1]) {
        
    				swapped = true;
    				swap(nums, j, j + 1);
    			}
    		}
    
    		//if no numbers being swapped, the array is fully sorted already. 
    		if (!swapped) {
        
    			break;
    		}
    	}
    
    	return nums;
    }
    
    private void swap(int[] nums, int i, int j) {
        
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }

### Selection Sort ###

*  原理
    
     *  将要排序的对象分成两部分，一部分是已排序的，一部分是未排序的。如果排序是由小到大，从后端未排序的部分选择一个最小值并放入前段已排序的部分的UI后一个。
 *  时间复杂度： O ( n 2 ) O(n^2) O(n2)， O ( n 2 ) / 2 O(n^2) / 2 O(n2)/2 swap worst case。

代码如下：

public void selectionSort(int[] nums) {
        
    	if (nums == null || nums.length <= 1) {
        
    		return;
    	}
    	
    	int min;
    
    	int len = nums.length;
    	for (int i = 0; i < len - 1; i++) {
        
    
    		min = i;
    		for (int j = i + 1; j < len; j++) {
        
    			if (nums[j] < nums[min]) {
        
    				min = j;
    			}
    		}
    
    		swap(nums, i, min);
    	}
    }
    
    private void swap(int[] nums, int i, int j) {
        
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }

### Insert Sort ###

*  原理
    
     *  将要排序的对象分作两部分，一个是已排序的，一个是未排序的。每次从后端未排序部分取得最前端的值，然后插入前段已排序的部分的适当位置。
 *  时间复杂度： O ( n 2 ) O(n^2) O(n2)， O ( n ) O(n) O(n) in the best case.

public void insertSort(int[] nums) {
        
    	if (nums == null || nums.length <= 1) {
        
    		return;
    	}
    	int len = nums.length;
    	
    	for (int i = 1; i < len; i++) {
        
    		int tmp = nums[i];
    		int j = i;
    		while (j > 0 && nums[j - 1] >= tmp) {
        
    			nums[j] = nums[j - 1];
    			j--;
    		}
    
    		nums[j] = tmp;
    	}
    }

--------------------

##  O ( n l o g n ) O(nlogn) O(nlogn) 算法 ##

### Merge Sort ###

*  原理
    
     *  Merge sort利用了divide-and-conquer的思想。
     *  将原有的排序问题对半分割
     *  利用相同的方法分别解决每个子问题
     *  最终将子问题的结果组合起来。
     *  这就是divide-and-conquer的三个重要步骤：divide-conquer-combine
 *  步骤
    
    1.  对第一部分进行排序
    2.  对第二部分进行排序
    3.  将两部分分别排好序的子数组merge到一起
 *  时间复杂度： O ( n 2 ) O(n^2) O(n2) on average。

算法如下：

public int[] mergeSort(int[] nums) {
        
    	if (nums == null || nums.length <= 1) {
        
    		return nums;
    	}
    
    	int len = nums.length;
    
    	int mid = len / 2;
    
    	int[] left = new int[mid];
    	int[] right = new int[len - mid];
    
    	copyArray(nums, left, 0, mid - 1);
    	copyArray(nums, right, mid, len - 1);
    
    	left = mergeSort(left);
    	right = mergeSort(right);
    	
    
    	return merge(left, right);
    }
    
    private int[] merge(int[] left, int[] right) {
        
    	int[] merged = new int[left.length + right.length];
    
    	int index_left = 0;
    	int index_right = 0;
    	int index_m = 0;
    
    	while (index_left < left.length && index_right < right.length) {
        
    		if (left[index_left] < right[index_right]) {
        
    			merged[index_m] = left[index_left++];
    		} else {
        
    			merged[index_m] = right[index_right++];
    		}
    
    		index_m++;
    	}
    
    	if (index_left < left.length) {
        
    		for (int i = index_left; i < left.length; i++) {
        
    			merged[index_m++] = left[i];
    		}
    	} else {
        
    		for (int i = index_right; i < right.length; i++) {
        
    			merged[index_m++] = right[i];
    		}
    	}
    
    	return merged;
    }
    
    private void copyArray(int[] nums, int[] target, int start, int end) {
        
    	int index = 0;
    	for (int i = start; i <= end; i++) {
        
    		target[index++] = nums[i];
    	}
    }

### Quick Sort ###

*  原理
    
     *  找一个pivot，将原数组分成两部分，然后对每一部分重复这个过程直到每一个元素都被选为pivot一次并得到处理。
 *  步骤
    
     *  选取一个pivot
     *  将原数组分成三部分：
        
         *  第一部分：所有小于pivot的元素
         *  第二部分：所有大于等于pivot的元素
         *  第三部分：pivot自己
     *  对第一部分和第二部分进行quick sort

代码如下：

public void quickSort(int[] nums) {
        
    	if (nums == null || nums.length <= 1) {
        
    		return;
    	}
    
    	quickSortHelper(nums, 0, nums.length - 1);
    }
    
        private void quickSortHelper(int[] nums, int start, int end) {
        
            if (start >= end) return;
            
            int pivot = nums[end];
            int pivotIndex = partition(nums, start, end, pivot);
            quickSortHelper(nums, start, pivotIndex - 1);
            quickSortHelper(nums, pivotIndex + 1, end);
        }
        
        private int partition(int[] nums, int start, int end, int pivot) {
        
            int p1 = start, p2 = end;
            while (true) {
        
                while (p1 < p2 && nums[p1] < pivot) p1++;
                while (p1 < p2 && nums[p2] > pivot) p2--;
                
                if (p1 >= p2) {
        
                    break;
                } else {
        
                    swap(nums, p1, p2);
                }
            }
            
            swap(nums, p1, end);
            return p1;
        }
        
        private void swap(int[] nums, int p1, int p2) {
        
            int tmp = nums[p1];
            nums[p1] = nums[p2];
            nums[p2] = tmp;
        }
    }

对于quick sort，需要注意的是其时间复杂度不一定总是 O ( n l o g n ) O(nlogn) O(nlogn)，在最坏情况下其时间复杂度是 O ( n 2 ) O(n^2) O(n2)。当quick sort每次都将数组分割成两个长度分别为 n − 1 n-1 n−1和 0 0 0的子数组时出现。这种情况会在数组是正序或者倒叙排列时出现。此时 T ( n ) = T ( n − 1 ) + O ( n ) T(n) = T(n-1) + O(n) T(n)=T(n−1)\+O(n)，从而使得时间复杂度为 O ( n 2 ) O(n^2) O(n2)。那么我们怎么解决这个问题呢？  
可以使用randomized quick sort来解决。在选取pivot的时候，我们不再使用最右边的元素作为pivot而是从数组中随机选择一个来作为pivot从而避免刚好选到最大值或者最小值的情况初选。通过这种方式，quick sort可以得到平均 O ( n l o g n ) O(nlogn) O(nlogn)的时间复杂度。

### Heap Sort ###

待完善

--------------------

\#搜索算法

##  O ( n ) O(n) O(n)算法 ##

### Linear Search ###

*  原理
    
     *  将全部元素清点一遍，寻找需要的值。
 *  时间复杂度： O ( n ) O(n) O(n)

public int lineSearch(int[] nums, int target) {
        
    	if (nums == null || nums.length == 0) {
        
    		return -1;
    	}
    	
    	for (int i = 0; i < nums.length; i++0 {
        
    		if (nums[i] == target) {
        
    			return i;
    		}
    	}
    	
    	return -1;
    }

##  O ( l o g n ) O(logn) O(logn)算法 ##

### Binary Search ###

*  原理
    
     *  每次搜索扔掉一半的元素，只有能够线性定位的结构能够使用。（比如LinkedList就不能使用，因为无法在O(1)时间内直接得到中间点。）
     *  数组必须是排好序的
 *  时间复杂度： O ( l o g n ) O(logn) O(logn)

public int binarySearch(int[] nums, int target) {
        
    	if (nums == null || nums.length == 0) {
        
    		return -1;
    	}
    	
    	int start = 0; 
    	int end = nums.length - 1;
    
    	while (start <= end) {
        
    		int mid = start + (end - start) / 2; 
    		//avoid int overflow
    	
    		if (nums[mid] == target) {
        
    			return mid;
    		}
    		if (nums[mid] < target) {
        
    			start = mid + 1;
    		}
    		if (nums[mid] > target) {
        
    			end = mid - 1;
    		}
    	}
    	
    	return -1;
    }

### Quick Select ###

参见[快速选择算法][Link 1]。

[Link 1]: https://blog.csdn.net/Yaokai_AssultMaster/article/details/68878950