简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
排序可视化
SelectionSort
选择排序很简单，所有的排序算法在前面的博客都有讲解：
选择排序很简单，遍历所有元素，查看一下他们的之后最小的元素和当前元素交换即可。模板函数使用上面的swing模板。为了更清楚显示出排序的过程，可以用不同颜色代表排好序和未排好序的。
int w = canvasWidth / data.N(); AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue); for (int i = 0; i < data.N(); i++) { if (i < data.orderIndex) { AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red); } else { AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey); } if (i == data.currentIndex) { AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Indigo); } if (i == data.currentComperent) { AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue); } AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i)); } } Frame的画图函数主要构成部分，其余的都是模板，为了抽象性，所以把selection的数据集中起来形成一个新的类，包括了生成数据等等。 public class SelectionSortData { private int[] numbers; public int orderIndex = -1; public int currentIndex = -1; public int currentComperent = -1; public SelectionSortData(int N, int randomBound) { numbers = new int[N]; for (int i = 0; i < N; i++) { numbers[i] = (int) (Math.random() * randomBound) + 1; //System.out.println(numbers[i]); } } public void setData(int orderIndex, int currentComperent, int currentIndex){ this.currentIndex = currentIndex; this.currentComperent = currentComperent; this.orderIndex = orderIndex; } public int N(){ return numbers.length; } public int get(int index){ if (index < 0 || index >= numbers.length){ throw new IllegalArgumentException("index is illgel!"); } return numbers[index]; } public void swap(int i, int j){ int t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } }
在这个数据类里面有三个属性，分别是已经排好序的索引，当前最小值，当前正在比较的索引。在渲染过程中需要改变就是这几个颜色了。所以动态的效果主要来源就是通过改变着几个值即可。
private void run() { data.setData(0,-1,-1); frame.render(data); AlgorithmHelper.pause(DELAY); for (int i = 0; i < data.N(); i++) { int midIndex = i; data.setData(i, -1, midIndex); frame.render(data); AlgorithmHelper.pause(DELAY); for (int j = i+1; j < data.N(); j++) { data.setData(i, j, midIndex); frame.render(data); AlgorithmHelper.pause(DELAY); if (data.get(j) < data.get(midIndex)){ midIndex = j; data.setData(i, j, midIndex); frame.render(data); AlgorithmHelper.pause(DELAY); } } data.swap(i, midIndex); data.setData(i+1, -1, -1); frame.render(data); AlgorithmHelper.pause(DELAY); } data.setData(data.N(), -1,-1); frame.render(data); AlgorithmHelper.pause(DELAY); }
查看一下效果：
InsertionSort
插入排序也很简单，没有涉及到递归操作等等。每遍历一个元素，看看这个元素和之前比较过的位置是在那里，像打牌的时候插排一样。和之前的查找一样，已经排好序的位置就直接用红色表示，当前对比位置用蓝色表示。首先是画图paintComponent：
int w = canvasWidth / data.N(); for (int i = 0; i < data.N(); i++) { if (i < data.orderIndex){ AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Red ); }else { AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.Grey); } if (i == data.currentIndex){ AlgorithmHelper.setColor(graphics2D, AlgorithmHelper.LightBlue); } AlgorithmHelper.fillRectangle(graphics2D, i * w, canvasHeight - data.get(i), w - 1, data.get(i)); } }
和上面的选择排序差不多。
private void run() { setData(-1, -1); for (int i = 0; i < data.N(); i++) { setData(i, i); for (int j = i; j > 0 && data.get(j) < data.get(j - 1); j--) { data.swap(j, j - 1); setData(i+1, j-1); } setData(i, -1); } setData(data.N(), -1); } private void setData(int orderIndex, int currentIndex){ data.orderIndex = orderIndex; data.currentIndex = currentIndex; frame.render(data); AlgorithmHelper.pause(DELAY); }
都是常规操作。
MergeSort
归并排序本身的思路，面对一个数组想要让他排序，首先把数组分成两部分，用同样的算法把两边排序，最后归并两边。在划分的时候，划分到不能再划分为止。首先同样要有一个归并的数据类：
public class MergeData { private int[] numbers; public int l, r; public int mergeIndex; public MergeData(int N, int randomBound) { numbers = new int[N]; for (int i = 0; i < N; i++) { numbers[i] = (int) (Math.random() * randomBound) + 1; //System.out.println(numbers[i]); } } public int N(){ return numbers.length; } public int get(int index){ if (index < 0 || index >= numbers.length){ throw new IllegalArgumentException("index is illgel!"); } return numbers[index]; } public void set(int index, int num){ if (index < 0 || index >= numbers.length){ throw new IllegalArgumentException("index is illgel!"); } numbers[index] = num; } public void swap(int i, int j){ int t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } }
用l和r来表示正在归并的数组范围，mergeIndex表示已经进行归并了的集合。归并整个过程前面的博客有写，不再复述了。
private void run() { setData(-1, -1, -1 ); Merge(0, data.N()-1); setData(0, data.N()-1, -1); } private void Merge(int l, int r) { if (l >= r) { return; } setData(l, r, -1); int mid = (l + r) / 2; Merge(l, mid); Merge(mid + 1, r); merge(l, r, mid); } private void merge(int l, int r, int mid) { int[] array = new int[r - l + 1]; for (int i = l; i <= r; i++) { array[i - l] = data.get(i); } int i = l, j = mid + 1; int index = l; while (i <= mid && j <= r) { if (array[i - l] < array[j - l]) { data.set(index, array[i - l]); i++; index++; } else { data.set(index, array[j - l]); j++; index++; } setData(l, r, index); } if (i <= mid) { for (int k = i; k <= mid; k++) { data.set(index, array[k - l]); index++; setData(l, r, index); } } else if (j <= r) { for (int k = j; k <= r; k++) { data.set(index, array[k - l]); index++; setData(l, r, index); } } }
效果：
QuickSort
快速排序，快速排序是在平均情况下比较快的算法了。每一次把第一个元素作为标定的位置，把这个位置放到合适的位置即可。首先还是需要一个快拍数据类：
public class QuickSortData { private int[] numbers; public int l, r; public int Index; public QuickSortData(int N, int randomBound) { numbers = new int[N]; for (int i = 0; i < N; i++) { numbers[i] = (int) (Math.random() * randomBound) + 1; //System.out.println(numbers[i]); } } public int N(){ return numbers.length; } public int get(int index){ if (index < 0 || index >= numbers.length){ throw new IllegalArgumentException(index + "index is illgel!"); } return numbers[index]; } public void set(int index, int num){ if (index < 0 || index >= numbers.length){ throw new IllegalArgumentException("index is illgel!"); } numbers[index] = num; } public void swap(int i, int j){ int t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; } }
和前面的归并排序一样，l和r用不同的颜色。
private void run() { setData(-1, -1, -1); QuickSort(0, data.N() - 1); setData(0, data.N() - 1, -1); } private void QuickSort(int l, int r) { if (l >= r) { return; } setData(l, r, -1); int mid = partition(l, r); QuickSort(l, mid - 1); QuickSort(mid + 1, r); frame.render(data); AlgorithmHelper.pause(DELAY); } private int partition(int l, int r) { int v = data.get(l); int i = l + 1; int j = r; setData(l, r, l); while (true) { while (i <= r && data.get(i) < v) { i++; } while (j >= l + 1 && data.get(j) > v) { j--; } if (i > j) { break; } data.swap(i, j); setData(l, r, l); i++; j--; } data.swap(j, l); setData(l, r, j); return j; }
和前面基本一致。
|今日打卡主题
第n天打卡，你熟悉的排序算法有哪些？留言写出来（希望大家走心打卡，让意见纠正传播）
