关于一道1到N自然数排序的华为面试题的疑问,该如何解决
日期：2014-05-20 浏览次数：20825 次
关于一道1到N自然数排序的华为面试题的疑问
首先声明，小弟才疏学浅，java水平不高。
看到网上有关这道排序题，有点疑问。具体题目如下：
有N个大小不等的自然数（1--N），请将它们由小到大排序。
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
看到网上有好多高手解答，例如：
int cnt = 0;//辅助变量，不是算法组成部分
void sort(int arr[], int n){
int t; /**//*临时变量：空间复杂度O(1)*/
//可以证明这个算法每次交换必然将一个数字正确安排到位，而且最多只有N次交换。
//具体体现在cnt的值上，所以虽然是二重循环仍然是时间复杂度O(n)
for (int i = 1; i <= n; i++){
while(arr[i] != i){
t = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = t;
++cnt;
}
}
}
小弟有个疑问，就是具体体现在cnt的值上，这指的到底是啥意思？如果没有这个值的话这个的算法复杂度就不是n了？有这个值怎么是n的？
小弟的实现：
//据说时间复杂度是o(n)的算法
public class OnSort {
public static void main(String[] args) {
int[] array = new int[] { 7, 6, 5, 4, 3, 2, 1 };
sort(array);
}
public static void temp(int[] arr) {
int temp;
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i + 1) {
temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[temp - 1] = temp;
}
}
}
public static void sort(int[] arr) {
temp(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
这个的复杂度和上面贴出来的有什么区别呢？
希望大虾们不吝赐教
------解决方案--------------------
cnt就是起到一个计数的作用，计算交换了多少次，完全可以不要
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
我又写了个JAVA的算法,与LZ的算法一样,复杂就是O(2n).main里有生成乱序的方法
首先声明，小弟才疏学浅，java水平不高。
看到网上有关这道排序题，有点疑问。具体题目如下：
有N个大小不等的自然数（1--N），请将它们由小到大排序。
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
看到网上有好多高手解答，例如：
int cnt = 0;//辅助变量，不是算法组成部分
void sort(int arr[], int n){
int t; /**//*临时变量：空间复杂度O(1)*/
//可以证明这个算法每次交换必然将一个数字正确安排到位，而且最多只有N次交换。
//具体体现在cnt的值上，所以虽然是二重循环仍然是时间复杂度O(n)
for (int i = 1; i <= n; i++){
while(arr[i] != i){
t = arr[arr[i]];
arr[arr[i]] = arr[i];
arr[i] = t;
++cnt;
}
}
}
小弟有个疑问，就是具体体现在cnt的值上，这指的到底是啥意思？如果没有这个值的话这个的算法复杂度就不是n了？有这个值怎么是n的？
小弟的实现：
//据说时间复杂度是o(n)的算法
public class OnSort {
public static void main(String[] args) {
int[] array = new int[] { 7, 6, 5, 4, 3, 2, 1 };
sort(array);
}
public static void temp(int[] arr) {
int temp;
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i + 1) {
temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[temp - 1] = temp;
}
}
}
public static void sort(int[] arr) {
temp(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
这个的复杂度和上面贴出来的有什么区别呢？
希望大虾们不吝赐教
------解决方案--------------------
cnt就是起到一个计数的作用，计算交换了多少次，完全可以不要
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
------解决方案--------------------
我又写了个JAVA的算法,与LZ的算法一样,复杂就是O(2n).main里有生成乱序的方法
- Java code
import java.util.Arrays;
import java.util.Random;
/**
* 有N个大小不等的自然数（1--N），请将它们由小到大排序。 要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
*
* @author chouy
*/
public class SortArrayFrom1toN extends Base
{
public static int N = 5000;
public static Random random = new Random();
public static void main(String[] args)
{
int[] is = new int[N];
for (int i = 0; i < is.length; i++)
{
is[i] = i;
}
// 打乱顺序
int tmp;
for (int i = 0; i < is.length; i++)
{
int j = random.nextInt(N);
tmp = is[i];
is[i] = is[j];
is[j] = tmp;
}
info(Arrays.toString(is));
info(Arrays.toString(new SortArrayFrom1toN().sort(is)));
}
/**
* 用交换的方法进行排序.<br>
* 交换方法:交换回来的数如果不应该在当前位置,则再把它与它应该在的位置交换
*
* @param array
* @return
*/
public int[] sort(int[] array)
{
int exchangeTimes = 0; // 比较计数器
int tmp;
for (int i = 0; i < array.length; i++)
{
if (array[i] != i)
{
tmp = array[array[i]];
array[array[i]] = array[i];
array[i] = tmp;
i--;
exchangeTimes++;
}
}
debug("exchangeTimes = " + exchangeTimes);
return array;
}
}
------解决方案--------------------
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
