我运行Quicksort 10次,得到平均时间.我对Qicksort/Insertion排序组合做同样的事情,它似乎比quicksort慢.
这是我调用InsertionSort的代码部分
public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) {
int indexofpartition;
if(max - min > 0) {
if( (max - min) <= 10) {
// Use InsertionSort now
InsertionSort.sort(data);
return;
} else {
indexofpartition = findPartition(data, min, max);
OptQSort2(data, min, indexofpartition - 1);
OptQSort2(data, indexofpartition + 1, max);
}
}
}
常规Quicksort与上面的代码片段相同,但没有调用InsertionSort的if条件.
FindPartition如下:
public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) {
int left, …我正在学习数据结构和算法的基础课程,我们使用的书是CLRS的开创性工作.我在理解循环不变量时遇到一些问题,如第2.1章:插入排序中所述.
这本书说:
在第1-8行的for循环的每次迭代开始时,子目标A [1..j -1]由最初在A [1..j-1]中的元素组成,但是按排序顺序.
现在,这让我很困惑.为什么在第一次迭代开始时它会成立？假设要排序的数组看起来像{5,2,4,6,1,3}.现在,当for循环的第一次迭代开始时,A [1 .. j-1]不是按排序顺序,但是当迭代结束时它就是.
我在这里错过了什么？
在这里给出的问题,我必须计算总数.使用插入排序对数组进行排序时所需的交换.
这是我的方法
#include <stdio.h>
int main()
{
int t, N, swaps, temp, i, j;
scanf("%d", &t);
while(t--){
scanf("%d", &N);
int arr[N];
swaps = 0;
for(i=0; i<N; ++i){
scanf("%d", &temp);
j=i;
while(j>0 && arr[j-1] > temp){
arr[j] = arr[j-1];
++swaps;
--j;
}
arr[j] = temp;
}
printf("%d\n", swaps);
}
return 0;
}
但是,这个soln超出了时间限制.
我怎样才能让它更快？
而且,这个问题的其他更好的解决方案是什么？
我正在尝试使用基于插入的排序算法对大型数据文件进行排序,代码运行正常,但输出不正确.我一遍又一遍地研究它完全无济于事,谁能看到我出错的地方？
public void sort(Comparable[] items) {
for (int i = 1; i < items.length; i++) {
Comparable temp = items[i];
int j = i - 1;
while (j >= 0 && items[j].compareTo(items[j]) > 0) {
items[j + 1] = items[j];
j = j - 1;
}
items[j] = temp;
}
}
我制作的一个示例数据文件是......
2
1
3
5
9
6
7
4
8
显然输出应该是1,2,3,4 ... - 但我得到1 3 5 9 6 7 4 8 8
如下所示是学校教授的基本插入排序算法.如果更改while循环参数的顺序,则不起作用.
public static int[] insertionSort(int[] A){
for(int i =1; i<A.length;i++){
int key = A[i];
int j = i;
while(j>0&&A[j-1]>key){
A[j]=A[j-1];
j--;
}
A[j]=key;
}
return A;
}
更改后(现在代码不会工作,它将给出java.lang.ArrayIndexOutOfBoundsException:-1 expection):
public static int[] insertionSort(int[] A){
for(int i =1; i<A.length;i++){
int key = A[i];
int j = i;
while(A[j-1]>key&&j>0){
A[j]=A[j-1];
j--;
}
A[j]=key;
}
return A;
}
如果有任何其他方法来实现相同的算法,以便条件循环语句的顺序无关紧要？
我正在准备软件开发人员的工作面试和复习算法问题.我无法弄清楚如何修改插入排序算法,以便它按排序顺序返回大小为n的数组的k个最小元素.
插入排序算法
for i = 1 to n
j = i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j = j - 1
在算法结尾添加for循环以获取前k个元素不计算在内.
我创建一个向量并用随机整数填充它.然后我打印出所有未排序的值并调用insertionSort().在此调用之后,应按排序顺序打印数字.我的程序一直在崩溃,我不知道为什么.
这是我的代码:
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
int listSize;
vector<int> intList()
{
cout << "How many numbers do you want to sort?\n";
cin >> listSize;
vector<int> list;
for (int i = 0; i < listSize; i++)
{
int random = rand() % 10001;
list.push_back(random);
}
return list;
};
void insertionSort(vector<int>& data)
{
int i, j, tmp;
for (i = 1; data.size(); i++)
{
j = i;
tmp = data[i];
while (j > …我有以下haskell语句的问题:
insertSort3 xs =
let sort3 [] ys = ys
sort3 (x:xs) ys = sort3 xs (insert x ys)
in sort3 xs []
我的编译器说:在输入'='上解析错误(错误发生在第三行).
出于某种原因,下面的C#插入排序代码返回索引超出范围异常.我会尝试将每个变量写出到控制台,但异常并没有让我这么做.我找不到解决方案,所以帮助升值.
using System;
using System.Collections.Generic;
class MainClass {
public static void Main (string[] args) {
int[] unsortedArray = {23, 19, 21, 44, 40, 60, 73, 80, 38, 55, 29, 78, 83, 61, 63, 9, 93, 6, 51, 11};
//Sets the unsorted list
Console.WriteLine ("Insertion Sort");
for (int i = 0; i < 20; i++) {
Console.Write(unsortedArray[i] + " , ");
}
//Displays a welcome message and the unsorted list
Console.WriteLine();
Console.WriteLine();
//Makes a gap between the unsorted and sorted list …我要疯了。我有4种排序算法的测试用例（气泡排序，选择排序，插入排序和合并排序）
我测试了有序数组，反向有序数组和随机数组。在每种情况下，插入排序都非常快。我测试了1k，5k和25k的数字。插入排序一定不能比合并排序快吗？对？（顺便说一句，在随机数数组的情况下，插入排序仍然更快，对于我的代码，插入排序始终是最快的算法。这肯定是错误的，但是哪里错了。。（我共享了所有代码）
Test Case for 1k Reversed Ordered Array: (in milis)
Bubble Sort run time: 512
Selection Sort run time: 154
Insertion Sort Run time: 1
Merge Sort run time: 19
test case for 5k reversed ordered number (in milis):
Bubble Sort run time: 11768
Selection Sort run time: 3613
Insertion Sort Run time: 4
Merge Sort run time: 100
Test Case for 25 k reversed ordered array
Bubble Sort run time: 303249
Selection Sort run time: 90469
Insertion Sort …