常见的排序算法及实现

-
本文配合visualgo食用更佳
  • 堆排序
  • 快速排序
  • 归并排序
  • 冒泡排序
  • 选择排序
  • 插入排序

堆排序

一般用一维数组来实现，为方便下标为0的位置空出，数据内容从下标为1开始。(如果要从0开始也是可行的)
迭代下面步骤：
  1. 调整乱序数组为一个大顶堆
  2. 交换下标为1（即最大的元素）与下标最后的元素内容，这时不满足堆的定义
  3. 调整剩余部分为大顶对
public class heapsort {
 public static void main(String args[]) {
  int[] num = new int[] { -1, 49, 38, 65, 97, 76, 13, 55 };
  sort(num);
  for (int i : num) {
   System.out.print(i + " ");
  }
 }
 static void heapAdjust(int start, int end, int[] array) {
  int temp = array[start];
  for (int j = 2 * start; j <= end; j *= 2) {
   if (j < end) {
    // 说明还有右子树
    if (array[j] < array[j + 1])
     j += 1;
    // 让j指向左右子树中较大的那个
   }

   if (temp >= array[j])
    // 满足大顶堆的要求不需要调整
    break;

   array[start] = array[j];
   // 调整顶端与子树内容
   start = j;
   // 继续循环
  }
  array[start] = temp;
 }

 static void sort(int[] num) {
  int N = num.length;
  for (int i = (N - 1) / 2; i >= 1; i--) {
   heapAdjust(i, N - 1, num);
  }
  /**
   * 对于一个已经调整好的大顶堆 这里要做的是交换顶端与最后一个节点的内容 然后继续调整从1到新的结尾的内容
   */
  for (int i = N - 1; i > 1; i--) {
   int temp = num[i];
   num[i] = num[1];
   num[1] = temp;
   heapAdjust(1, i - 1, num);
  }
 }
}

快速排序

这是一个分治的过程。
对于一个一维数组，每次找到一个基准(base)。把小于base的所有数放左边，大于base的所有数放右边。这时base所处的位置就是其最终位置，然后递归快速排序两边的数组。(两边的数组可以为空)
精髓在与partition，每次找到那个数应该在的位置，把原数组分成两部分。直接看代码不理解的找个例子脑子跑一遍就通了。
import java.util.Arrays;
public class QuickSort {
 public static void main(String[] args) {
  int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
  quickSort(array, 0, array.length - 1);
  System.out.println(Arrays.toString(array));
 }

 public static void quickSort(int[] array, int start, int end) {
  if(start<end){
   int par = partition(array, start, end);
   quickSort(array, start, par-1);
   quickSort(array, par+1, end);
  }
 }

 public static int partition(int[] array, int start, int end) {
  int position = start - 1;
  int base = array[end];
  for (int i = start; i < end; i++) {
   if(array[i] <= base ){
    position ++;
    swap(array, i, position);
   } 
  }
  swap(array,position+1,end);
  return position + 1;
 }
 
 public static void swap(int[] array,int a,int b){
  int temp = array[a];
  array[a] = array[b];
  array[b] = temp;
 }
}

归并排序

这也是一个利用分治法来实现的排序，归并在于：把两个有序的数组元素之间相互比大小，把小的元素放入新的数组中，最后返回新数组即是原先两个有序数组的排序。
利用递归，先把给定数组分解成长度为1，这样就可以看作是一个有序数组了，然后两两进行归并。
精髓在于维护三个指针low,mid,high 这三个指针把我们要考虑的数组分解成了两个部分[low~mid]和[mid+1~high]
import java.util.Arrays;
public class MergeSort {
 static void sort(int[] nums, int low, int high) {
  if (low >= high)
   return;
  int mid = (low + high) / 2;
  sort(nums, low, mid);
  sort(nums, mid + 1, high);
  merge(nums, low, mid, high);
 }

 static void merge(int[] nums, int low, int mid, int high) {
  int[] temp = new int[high - low + 1];
  int k = 0;
  int i = low;
  int j = mid+1;
  while(i<= mid && j <= high){
   if(nums[i]<=nums[j]){
    temp[k++] = nums[i++];
   }else {
    temp[k++] = nums[j++];
   }
  }
  while(i<=mid){
   temp[k++] = nums[i++];
  }
  while(j<=high){
   temp[k++] = nums[j++];
  }
  for(int m = 0;m<temp.length;m++){
   nums[m+low] = temp[m];
  }
 }

 public static void main(String args[]) {
  int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
  sort(nums, 0, nums.length - 1);
  System.out.println(Arrays.toString(nums));
 }
}

冒泡排序

不解释 ＝＝
嗯 自从看到有这个网站visualgo之后就懒得自己写解释了 (逃
import java.util.Random;
public class Bubble {
 private static void swap(int[] array, int index1, int index2) {
  if (index1 >= 0 && index1 < array.length && index2 >= 0
    && index2 < array.length) {
   int tmp = array[index1];
   array[index1] = array[index2];
   array[index2] = tmp;
  }
 }

 public static void BubbleSort(int[] arr) {
  int len = arr.length;
  if (arr == null || len < 2)
   return;
  boolean swapped = true;
  while (swapped) {
   swapped = false;
   for (int i = 0; i < len - 1; i++) {
    if (arr[i] > arr[i + 1]) {
     swap(arr, i, i + 1);
     swapped = true;
    }
   }
   len--;
  }
 }

 public static void main(String[] args) {
  int[] arr = new int[10];
  int len = arr.length;
  Random rand = new Random();
  for (int i = 0; i < len; i++) {
   arr[i] = rand.nextInt(10);
  }
  for (int i : arr) {
   System.out.print(i + " ");
  }
  System.out.println();
  BubbleSort(arr);
  for (int i : arr) {
   System.out.print(i + " ");
  }

 }
}

选择排序

import java.util.Random;
public class select {
 public static void selectsort(int[] arr) {
  if (arr == null || arr.length < 2) {
   return;
  }
  int len = arr.length;
  int counter = 0;
  while (counter < len) {

   int min = counter;
   for (int i = counter; i < len; i++) {
    min = arr[i] < arr[min] ? i : min;
   }
   swap(arr, counter, min);
   counter++;
  }

 }

 public static void main(String args[]) {
  int[] arr = new int[10];
  int len = arr.length;
  Random rand = new Random();
  for (int i = 0; i < len; i++) {
   arr[i] = rand.nextInt(10);
  }
  for (int i : arr) {
   System.out.print(i + " ");
  }
  System.out.println();
  selectsort(arr);
  for (int i : arr) {
   System.out.print(i + " ");
  }
 }

 private static void swap(int[] array, int index1, int index2) {
  if (index1 >= 0 && index1 < array.length && index2 >= 0
    && index2 < array.length) {
   int tmp = array[index1];
   array[index1] = array[index2];
   array[index2] = tmp;
  }
 }
}

插入排序

import java.util.LinkedList;
import java.util.Random;
public class insert {
 public static Object[] insertsort(Integer[] array) {
  LinkedList<Integer> linkedList = new LinkedList<Integer>();
  if (array == null || array.length < 2) {
   return linkedList.toArray();
  }
  int len = array.length;
  linkedList.add(Math.min(array[0], array[1]));
  linkedList.add(Math.max(array[0], array[1]));
  if (len == 2) {
   return linkedList.toArray();
  }
  for (int i = 2; i < len; i++) {
   int position = 0;
   for (int j = 0; j < linkedList.size(); j++) {
    if (linkedList.get(j) <= array[i]) {
     position++;
    }
   }
   linkedList.add(position, array[i]);
  }
  return linkedList.toArray();
 }

 public static void main(String args[]) {
  Integer[] arr = new Integer[10];
  int len = arr.length;
  Random rand = new Random();
  for (int i = 0; i < len; i++) {
   arr[i] = rand.nextInt(10);
  }
  for (int i : arr) {
   System.out.print(i + " ");
  }
  System.out.println();

  for (Object i : insertsort(arr)) {
   System.out.print((Integer) i + " ");
  }
 }
}

Comments

Post a Comment

Popular posts from this blog

Malware Report: iauzzy.exe

-
Image
Malware report of iauzzy.exe Summary This malware will create a file named ‘qqt.exe’ under the %WinDir%. This is the exact malicious executable file. qqt.exe is able to communicate to the ‘Command & Control’ server via IRC. The controller behind is able to execute any code; reboot the infected machine; clean the malware itself, etc.
Read more

Malware Report: withme.exe

-
Image
Malware Report withme.exe Summary This Withme.exe will drop a executable file ‘A-1980682553.exe’ to the location %AppData%. Also It will add itself to runonce registry. This is the exact malware. It’s able to communicate with C2 server, which domain is ‘sexwithme.info’ wia port 6667.
Read more

根因分析之iDice 文章复现

-
Image
1 Abstract  原文 给的场景是对于大规模集群的运维，当一条issue被上报的时候，通常会带上一些attribute，比如时间，软件版本，所处的国家，城市，具体在哪个机房，浏览器，操作系统等等。 在平时的时候，每天的上报的issue数量应该是差不多的，但有些时候，报错数量会突然上升，对于运维人员定位到问题所在往往很花时间。背后的问题可能是某个attribute或者某几个attributes的组合，文章称为effective combination。 这里通过三个步骤来从所有的attribute combination中找到最后可能引发报错激增的effective combination。 2 Challenge 想要找到所有effective combination的最暴力的做法就是，枚举所有attribute combination，然后以某种方式来衡量它对于总体issue激增的关系。 这里主要的问题在于搜索空间过大，本文最大的创新在于对搜索空间的剪枝。如果一共有m个attribute，那一共的组合方式就是(2^m - 1)种 3 Approach 文章把整个流程主要分成三个步骤（用做剪枝）和一个结果排序 Impact based Pruning: 基于影响的用户量做剪枝（不含时间信息） Change Detection based Pruning: 基于时间线上的突变来剪枝（时间序列处理） Isolation Power based Pruning: 计算一个类似信息熵增益的值来判断这个attribute combination的区分度 Result Ranking: 计算这个attribute combination对于全局的显著性 3.1 Impact based Pruning 对于一个effective combination而言，它必须影响足够多的用户。所以这里定一个threshold来过滤掉一些不可能的参数组合。（排除时间这个维度） 这里的目的是 寻找closed frequent itemsets，文章里的没有对算法进行详细描述，就说用BFS-based closed itemset mining algorithm。 在复现的时候，我先用了现成的找 frequent itemset 的算法（ Apriori /FPMax/ FPGrowt
Read more