算法：【排序】（待完善）
一、归并排序（分而治之）
模板
class Solution {
// 归并排序
public int[] sortArray(int[] nums) {
if(nums == null || nums.length == 0)
return nums;
mergesort(nums, 0, nums.length-1);
return nums;
}
public void mergesort(int[] nums, int low, int high){
if(low < high){
int mid = low + (high-low)/2;
mergesort(nums, low, mid);
mergesort(nums, mid+1, high);
merge(nums, low, mid, high);
}
}
public void merge(int[] nums, int low, int mid, int high){
int[] tmp = new int[high-low+1];
int l = low, r = mid+1;
int k = 0;
while(l <= mid && r <= high){
if(nums[l] <= nums[r]){
tmp[k++] = nums[l++];
}else{
tmp[k++] = nums[r++];
}
}
while(l <= mid)
tmp[k++] = nums[l++];
while(r <= high)
tmp[k++] = nums[r++];
for(int i=0; i<tmp.length; i++){
nums[low+i] = tmp[i];
}
}
}1.1 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
输入: [7,5,6,4]
输出: 5
// 归并排序
public class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;
if (len < 2) {
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) { // 表明数组已经有序，没有逆序对了
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
} 1.2 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。输入：strs = ["flower","flow","flight"]
输出："fl"
class Solution {
// 1.横向扫描
// public String longestCommonPrefix(String[] strs) {
// if(strs == null || strs.length == 0)
// return "";
// String prefix = strs[0];
// for(int i=1; i<strs.length; i++){
// prefix = process(prefix, strs[i]);
// if(prefix == "")
// return prefix;
// }
// return prefix;
// }
// 2.纵向扫描
// public String longestCommonPrefix(String[] strs) {
// if(strs == null || strs.length == 0)
// return "";
// int len = strs[0].length();
// for(int i=0; i<len; i++){
// char c = strs[0].charAt(i);
// for(int j=0; j<strs.length; j++){
// if(i == strs[j].length() || strs[j].charAt(i) != c)
// return strs[0].substring(0, i);
// }
// }
// return strs[0];
// }
// 3. 分而治之
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0)
return "";
return megerprocess(strs, 0, strs.length-1);
}
public String megerprocess(String[] str, int left, int right){
if(left == right){
return str[left];
}else{
int mid = left + (right - left)/2;
String leftInfo = megerprocess(str, left, mid);
String rightInfo = megerprocess(str, mid+1, right);
return process(leftInfo, rightInfo);
}
}
public String process(String str1, String str2){
int len = Math.min(str1.length(), str2.length());
int index = 0;
while(index < len && str1.charAt(index) == str2.charAt(index))
index++;
return str1.substring(0, index);
}
}二、快速排序
模板
class Solution {
// 快速排序
public int[] sortArray(int[] nums) {
if(nums == null || nums.length == 0)
return nums;
quicksort(nums, 0, nums.length-1);
return nums;
}
public void quicksort(int[] nums, int low, int high){
if(low < high){
int mid = partition(nums, low, high);
quicksort(nums, low, mid-1);
quicksort(nums, mid+1, high);
}
}
public int partition(int[] nums, int low, int high){
int base = nums[low];
while(low < high){
while(low < high && nums[high] >= base)
high--;
nums[low] = nums[high];
while(low < high && nums[low] <= base)
low++;
nums[high] = nums[low];
}
nums[low] = base;
return low;
}
}2.1 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
输入: [10,2]
输出: "102"
解题思路：
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
public void quickSort(String[] strs, int low, int high){
if(low < high){
int mid = partition(strs, low, high);
quickSort(strs, low, mid-1);
quickSort(strs, mid+1, high);
}
}
public int partition(String[] strs, int low, int high){
String base = strs[low];
while(low < high){
while(low < high && (strs[high] + base).compareTo(base + strs[high]) >= 0)
high--;
strs[low] = strs[high];
while(low < high && (strs[low] + base).compareTo(base + strs[low]) <= 0)
low++;
strs[high] = strs[low];
}
strs[low] = base;
return low;
}
}
