长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的swap 请设计并实现排序。
google笔试小题。题目来源:http://wenku.baidu.com/view/5aa818dda58da0116c17498b.html休闲小题。
2个key
一个是只能与0 swap,另一个是数组的下标和值是一一对应的。
第二个容易被忽略。所以读到一个元素时,如果值和下标不等,那么可以直接把这个元素的值放到正确位置上去,目标位置的值挪回来。当然这个过程要借助元素0来完成。

假设输入是 2,0,3,1
step 1
遍历数组,找出值为0的元素,和num[0]交换
0 2 3 1

step 2
如果num[1]下标和值匹配,考虑下一个,否则
尝试把num[1]的值借助num[0]放入正确的位置
3 2 0 1 --》  3 0 2 1 --》 0 3 2 1

step 3
重复 step 2,直到 num[1]正确被放置了 1

step 4
num[1]处理完,step2处理下一个元素num[2],直到所有元素的位置和值都匹配

    void swap(int* num, int a, int b){
if(a == b) return;
int tmp = num[a];
num[a] = num[b];
num[b] = tmp;
} void sort(int* num, int size){
int i = ;
//move 0 to num[0]
for(;i<size;i++){
if(num[i] == ){
swap(num, i, );
}
}
i = ;
while(i<size){
//postion matched value
if(num[i] == i){
i++;
}
//postion mismatch value, then need to place value to the correct postition and continue
else{
int tarpos = num[i];
swap(num, , tarpos); // num[tarpos] = 0
swap(num, tarpos,i); // num[i] = 0
swap(num, , i); // num[0] = 0
}
}
} int main(){
int input[] = {,,,};
sort(input, );
int t = ;
for(;t<;t++)
printf("%d->",input[t]);
printf("n");
}

原文地址:http://blog.chinaunix.net/uid-26456800-id-3512430.html

最新文章

  1. 在Ubuntu|CentOS上安装Shutter截图工具及快捷键设置
  2. css多行显示省略号
  3. myeclipse编译、输出
  4. 51nod 1428 活动安排问题(优先队列)
  5. Mahout 介绍
  6. maven遇到的问题
  7. [转]Excel 取汉字拼音首位
  8. Shell脚本学习入门(一)
  9. cmd执行mssql脚本或者执行mysql脚本
  10. 最短路径之Dijkstra算法及实例分析
  11. ☀【Node】处理POST请求
  12. 真机调试报错:Could not find Developer Disk Image 或 Could not locate device support files.
  13. python版去UTF-8 BOM
  14. openwrt驱动与应用程序的联系
  15. CodeForces 609A USB Flash Drives
  16. OpenSceneGraph几个重要功能节点练习
  17. 【学习笔记】JS知识点整理
  18. xampp 丢失api-ms-win-crt-runtimel1-1-0.dll 解决方案
  19. tcp为什么是三次握手
  20. bitcoin源码解析 - 交易 Transcation (一)

热门文章

  1. TCP之LAST_ACK状态
  2. Tracer使用
  3. Python 抓取数据存储到Mysql中
  4. PHP 页面中实现数据的增删改查
  5. leetcode-easy-trees-102. Binary Tree Level Order Traversal-YES
  6. leetcode 103二叉树的锯齿形层次遍历
  7. leetcode241 为运算表达式设计优先级
  8. 【8】ie css hack
  9. Kubernetes Controller执行框架解析
  10. cocos2dx基础篇(5) 按钮