排序算法
1. 快速排序
排序数组
递归法
public void sort(int[] nums, int l, int r){
if(l < r) {
int i = l, j = r, x = nums[l];
while(i < j) {
while(i < j && nums[j] >= x) j--;
nums[i] = nums[j];
while(i < j && nums[i] <= x) i++;
nums[j] = nums[i];
}
nums[i] = x;
sort(nums, l, i-1);
sort(nums, i+1, r);
}
}
非递归法
private static int partition(int[] nums, int start, int end)
{
int pivot = nums[start];
while (start < end) {
while (start < end && nums[end] >= pivot)
end--;
nums[start] = nums[end];
while (start < end && nums[start] <= pivot)
start++;
nums[end] = nums[start];
}
nums[start] = pivot;
return start;
}
public static void sort(int[] nums, int start, int end)
{
Stack<Integer> stack = new Stack<>();
stack.push(start);
stack.push(end);
while(!stack.isEmpty())
{
int right = stack.pop();
int left = stack.pop();
int mid = partition(nums, left, right);
if(left < mid-1)
{
stack.push(left);
stack.push(mid-1);
}
if(mid+1 < right)
{
stack.push(mid+1);
stack.push(right);
}
}
}
排序链表
1. 仅交换值
public void partition(ListNode head, ListNode tail){
if(head == tail || head.next == tail)
return head;
ListNode left = head, curr = head.next;
int pivot = head.val;
while(curr != tail){
if(curr.val < pivot){
left = left.next;
swap(left, curr);
}
curr = curr.next;
}
swap(head, left);
partition(head, left);
partition(left.next, tail);
}
void swap(ListNode n1, ListNode n2){
int tmp = n1.val;
n1.val = n2.val;
n2.val = tmp;
}
2. 节点交换
public ListNode partition(ListNode head){
if(head == null || head.next == null)
return head;
ListNode ls = new ListNode(0), l = ls, rs = new ListNode(0), r = rs, curr = head;
int pivot = head.val;
while(curr != null){
if(curr.val < pivot){
l.next = curr;
l = l.next;
}
else{
r.next = curr;
r = r.next;
}
curr = curr.next;
}
l.next = rs.next;
r.next = null;
ListNode right = partition(head.next);
head.next = null;
ListNode left = partition(ls.next);
curr = left;
while(curr.next != null)
curr = curr.next;
curr.next = right;
return left;
}
2. 堆排序
排序数组
public void sort(int[] nums){
int len = nums.length();
for(int i = len/2-1; i >= 0; i--){
adjust(nums, i, len);
}
for(int i = len-1; i > 0; i--){
swap(nums, 0, i);
adjust(nums, 0, i);
}
}
private void adjust(int[] nums, int i, int len){
int tmp = nums[i];
for(int k = 2*i+1; k < len; k = 2*k+1){
if(k+1 < len && nums[k+1] > nums[k]){
k++;
}
if(tmp < nums[k]){
swap(nums, i, k);
i = k;
}
else break;
}
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
3. 冒泡排序
实现
public void sort(int[] nums) {
int len = nums.length;
boolean flag;
for(int i = len - 1; i > 0; i--) {
flag = true;
for(int j = 0; j < i; j++) {
if(nums[i] > nums[i + 1]) {
swap(nums, i, i + 1);
flag = false;
}
}
if(falg) break;
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
时间复杂度：最好： O(n) ，最差： O(n^2) 。
稳定性：稳定。
4. 选择排序
实现
public void sort(int[] nums) {
int len = nums.length;
int min;
for(int i = 0; i < len; i++) {
min = i;
for(int j = i + 1; j < len; j++) {
min = nums[j] < nums[min] ? j : min;
}
if(min != i)
swap(nums, i, min);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
时间复杂度： O(n^2) 。
稳定性：不稳定。
5. 插入排序
实现
public void sort(int[] nums) {
int len = nums.length;
for(int i = 1; i < len; i++) {
for(int j = i; j > 0 && nums[j] < nums[j - 1]; j--)
swap(nums, j - 1, j);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
时间复杂度：最好： O(n) ，最差： O(n^2) 。
稳定性：稳定。
6. 希尔排序
实现
public void sort(int[] nums) {
int len = nums.length, gap = len;
while(true) {
gap /= 2;
for(int i = 0; i < gap; i++) {
for(int j = i + gap; j < len; j += gap) {
int tmp = nums[j];
int k = j - gap;
while(k >= 0 && nums[k] > tmp) {
nums[k + gap] = nums[k];
k -= gap;
}
nums[k + gap] = tmp;
}
}
if(gap == 1) break;
}
}
时间复杂度：最坏： O(n^2) 。
稳定性：不稳定。
7. 归并排序
实现
public int[] sort(int[] nums, int l, int r) {
if(l == r) return new int[]{nums[l]};
int mid = l + (r - l) / 2;
int[] left = sort(nums, l, mid);
int[] right = sort(nums, mid + 1, r);
int[] newArr = new int[left.length + right.length);
int i = 0, j = 0, k = 0;
while(i < left.length && j < right.length)
newArr[k++] = left[i] < right[j] ? left[i++] : right[j++];
while(i < left.length)
newArr[k++] = left[i++];
while(j < right.length)
newArr[k++] = right[j++];
return newArr;
}
时间复杂度： O(nlog n)
空间复杂度： O(n)
稳定性：稳定。