荷兰国旗演绎解决方案
在学习了初级排序、选择排序、插入排序和堆排序之后，从“古瑟拉”中的sedgewick 课程中进行了排序。
选择排序-最终排序顺序开始形成每次迭代。
插入排序-上升顺序(非最终)开始形成每一个迭代。
堆排序-插入排序的进攻性版本。
我有一个作业，在上面提到的课程中，在学习排序算法之后(如上所示)，
荷兰国旗。给定一个
n桶数组，每个桶包含一个红色、白色或蓝色的卵石，按颜色对它们进行排序。允许的操作是：swap(i,j)：swap在i桶中的鹅卵石和j中的卵石。color(i)：i桶中鹅卵石的颜色。 所需执行情况如下： 最多是n对color()的调用。 最多是n对swap()的调用。 固定的额外空间。
通过阅读这个问题，
从性能要求来看，我得到了一个提示，即n交换是必需的(最多)。从这个提示，我想，
1)插入排序，以确保n个交换的n对反转对。
2)假设储存在水桶中的颜色，如果有n个水桶，则很有可能类似的颜色会更靠近。这导致了部分排序数组的情况，如果反转<= cn的数量，数组会被部分排序。
基于上述两项结论，
问题：
1)
思维过程在演绎插入排序时是否正确，作为解决方案？
2)
散列颜色和插入颜色作为部分排序数组的哈希函数是什么？我需要线性探测方法吗？
3)为什么我们需要额外的空间？因为插入排序是就地算法。
注意:在编写代码之前，确认我的思维过程。
回答 3
Stack Overflow用户
发布于 2016-12-27 08:34:43
要详细说明这个问题的解决方案，您不需要提到算法。
相反，要熟悉Quick的分区例程实现--这将非常有用。
附注：
堆排序-插入排序的侵略性版本
不，你错了，这是完全不同的方法
您可以考虑Shell排序如何在内部利用插入排序。
Stack Overflow用户
发布于 2016-12-27 09:21:29
我不认为你应该(或需要)假设更靠近的水桶有更高的机会拥有相同的颜色。这个问题可以解决，保持两种颜色中第一种出现的指数(在排序中不被认为是“第一种”)。将颜色替换为值0、1、2，我相信此代码满足以下要求：
public class Z {
private static int first1, first2;
private static void swap(int[] v, int i, int j) {
int tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
private static void sort(int[] v) {
first1 = -1;
first2 = -1;
for(int i=0; i<v.length; i++) {
switch(v[i]) {
case 0:
if (first1 != -1) {
swap(v, i, first1);
if (first2 != -1) {
swap(v, i, first2);
first2++;
}
first1++;
} else if (first2 != -1) {
swap(v, i, first2);
first2++;
}
break;
case 1:
if (first2 != -1) {
swap(v, i, first2);
if (first1 == -1) {
first1 = first2;
}
first2++;
} else if (first1 == -1) {
first1 = i;
}
break;
case 2:
if (first2 == -1) {
first2 = i;
}
break;
}
}
}
public static String toString(int[] v) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for(int i=0; i<v.length; i++) {
sb.append(v[i]);
sb.append(" ");
}
sb.append("]");
return sb.toString();
}
public static void main(String[] args) {
int c = Integer.parseInt(args[0]);
int[] v = new int[c];
while(true) {
int[] tmp = v.clone();
System.out.print(toString(tmp) + "=>");
sort(tmp);
System.out.println(toString(tmp));
int prev = -1;
for(int j=0; j<tmp.length; j++) {
if (tmp[j] < prev) {
throw new Error();
}
}
int j;
for(j=0; j<c; j++) {
v[j]++;
if (v[j] == 3) {
v[j] = 0;
} else {
break;
}
}
if (j == c) {
break;
}
}
}
}Stack Overflow用户
发布于 2017-02-15 16:35:15
作为一种暗示，维基百科这样说，强调我的观点：
荷兰国旗问题是Edsger Dijkstra提出的计算机科学编程问题。荷兰国旗由三种颜色组成:红色、白色和蓝色。给定这三种颜色的球在一行中随机排列(球的实际数量不重要)，任务是将它们排列在一起，使所有颜色相同的球在一起，它们的集体颜色组按正确顺序排列。 这个问题的解决方案对于设计排序算法是有意义的；特别是，快速排序算法的变体必须对重复元素具有鲁棒性，它需要一个三向分区函数，对小于给定键(红色)、等于键(白色)和大于键(蓝色)的项进行分组。有几种解决方案具有不同的性能特征，可定制为具有少量或大量重复元素的数组排序。
(对于解决方案，本文也有伪码。用于算法)
https://stackoverflow.com/questions/41340528
复制相似问题
腾讯云开发者
