题目:一个数组中只有0,1,2三种元素,要求对这样的数组进行排序。
1.思路:
1.1思路1:
第一眼看到这样的题目,会举得非常简单,只需要两次遍历数组就可以完成了。第一次遍历,扫描数组中的元素,每次遇到0则count0++,遇到1则count1++,遇到2则count2++,这样一趟下来就能够统计出数组中0,1,2的个数了。然后第二次遍历的时候,只需要对数组进行重新赋值就可以了,从头开始赋值count0个0,count1个1,count2个2。最终完成对数组的排序。
1.2思路2:
既然是面试题,那么肯定不会让你这么简单就解决出来了的。面试官说,加入只能进行一次遍历怎么办,然后你就不知道了。
这道题目如果只能进行一次遍历,我们肯定会想到使用多指针。这种题目之前碰到过很多。类似折半查找需要设置两个指针,不过这道题目却需要三个指针,分别指向数组中0,1,2三个元素末尾。加入有排好序的数组{0,0,1,1,2,2},那么p0指向下标为1的那个0,p1指向下标为3的那个1,而p2则指向下标为5的那个2。
p0和p1从前往后扫描,p2从后往前扫描,
初始化时:
p0指向第一个非0元素,那么arry[p0]=1||2
p1指向第一个非1元素,那么arry[p1]=0||2
p2指向第一个非2元素,那么arry[p2]=0||1
假如:
arry[p0]==2,arry[p2]==0,交换两个元素
arry[p1]==2,arry[p2]==1,交换两个元素
arry[p0]==1,arry[p1]==0,交换两个元素
否则的话只可能是p0,p1,p2指向的三个数各不相同,那么进行如下赋值
arry[p0]==0,arry[p1]==1,arry[p2]==2。
假如经过上述swap以后出现i>k的情况,将k=i。(PS:2012-10-5)
2.代码示例
#include<iostream> #include<stdlib.h> using namespace std; void PrintArry(int arry[],int len) { for(int i=0;i<len;i++) cout<<arry[i]<<" "; cout<<endl; } void swap(int arry[],int i,int j) { int temp=arry[i]; arry[i]=arry[j]; arry[j]=temp; } void sort(int arry[],int len) { int i= 0;//头指针指向0 int j = len - 1;//尾指针指向2 int k = 0;//中间指针指向1 while(i <= j && k <= j && i <= k) { //i指向第一个非0值 while(arry[i] == 0){ i++; } //k指向第一个非1值 while(arry[k] == 1){ k++; } //j指向第一个非2值 while(arry[j] == 2){ j--; } if(i <= j && arry[j] == 0 && arry[i] == 2){ swap(arry,i,j); i++; j--; } else if(k <= j && arry[k] == 2 && arry[j] == 1){ swap(arry,k,j); k++; j--; } else if(i <= k && arry[k] == 0 && arry[i] == 1){ swap(arry,k,i); i++; k++; } else if(i < k && k < j){ arry[i] = 0; arry[k] = 1; arry[j] = 2; i++; k++; j--; } if(i>k) { k=i; } } } void main() { int arry[]={1,0,2,2,0,1,0,1}; int len=sizeof(arry)/sizeof(int); PrintArry(arry,len); sort(arry,len); PrintArry(arry,len); system("pause"); }
经试验sort函数好像还可以精简
void sort(int arry[],int len)
{
int i= 0;//头指针指向0
int k = 0;//中间指针指向1
int j = len - 1;//尾指针指向2
while(k <= j && i <= k)
{
//i指向第一个非0值
while(arry[i] == 0)
i++;
//k指向第一个非1值
while(arry[k] == 1)
k++;
//j指向第一个非2值
while(arry[j] == 2)
j--;
if(i > k)
k = i;
if(i < j && arry[j] == 0 && arry[i] == 2)
{
swap(arry,i,j);
}
else if(k <j && arry[k] == 2 && arry[j] == 1)
{
swap(arry,k,j);
}
else if(i < k && arry[k] == 0 && arry[i] == 1)
{
swap(arry,k,i);
}
else if(i < k && k < j)
{
arry[i] = 0;
arry[k] = 1;
arry[j] = 2;
}
}
}
相关推荐
1. 将待排序的数组不断分成两半,直到每个子数组只有一个元素。这一步被称为分解。 2. 对每个子数进行排序,可以使用任何有效的排序算法。这一步被称为求解。 3. 将所有已排序的子数组合并成一个有序的数组。这一步...
它使用递归的方式将数组不断划分为更小的子数组,直到每个子数组只有一个元素,然后再依次将这些子数组进行合并,从而实现排序。 merge 方法用于合并两个有序子数组。它借助两个辅助数组 leftArray 和 rightArray,...
1. 将待排序的数组不断分成两半,直到每个子数组只有一个元素。这一步被称为分解。 2. 对每个子数进行排序,可以使用任何有效的排序算法。这一步被称为求解。 3. 将所有已排序的子数组合并成一个有序的数组。这一步...
该数组的下标变量共有3×4个,即: a[0][0],a[0][1],a[0][2],a[0][3] a[1][0],a[1][1],a[1][2],a[1][3] a[2][0],a[2][1],a[2][2],a[2][3] 二维数组在概念上是二维的,即是说其下标在两个方向上变化, 下标变量在...
1. 分解:将待排序的数组不断分成两个子数组,直到每个子数组只有一个元素为止。 2. 合并:将相邻的两个子数组合并成一个有序数组,直到最后只剩下一个有序数组为止。 在合并的过程中,需要用到一个辅助数组来暂存...
1. 将n个元素建立初始堆,第一个节点放在数组下标1中,因此n个节点对应数组 a[1] ~ a[n],第 i 个节点的左孩子节点下标为 2i,右孩子节点为 2i + 1。 找到最后一个非叶子节点: 若节点 i 为最后一个非叶子节点,则 ...
插入排序 插入排序的基本思想:每次将一个待排序序列按其关键字大小插入到前面已经排好序的子序列中,知道全部记录插入完成。主要有直接插入排序、折半插入排序和...// 直接插入排序c实现,a表示数组,n表示数组大小 /**
设n=2,输入数据为:(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3, 20), (‘A’,4,25),(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。每一组输入数据包括...
1.快速排序的思想 先从数列中取出一个数作为基准数(简单起见就选第一个数) 分区过程:将比这个数大的数全放到他的右边,比他小的数全放到他的左边(分治) 再对左右两边的区重复第一步和第二部操作,直到各区间...
首先我们把整个数组拆分为有序区间和未排序区间,有序区间在插入排序一开始只有一个元素,就是数组的第一个元素。 接在有序区间之后的一个元素就是准备插入的元素,在图中就是标为绿色的元素,在有序区间内寻找位置...
文章目录1. 基本思想2. 代码实现2.1 递归实现2.2 优化—非递归实现3...归并排序与快速排序的思想基本一致,唯一不同的是归并排序的基准值是数组的中间元素 快排 Link:[排序算法] 6. 快速排序多种递归、非递归实现及性能
爱因斯坦曾出过这样一道数学题:有一条长阶梯,若每步跨2阶,则最后剩下1阶,若每步跨3阶,则最后剩下2阶,若每步跨5阶,则最后剩下4阶,若每步跨6阶,则最后剩下5阶,只有每步跨7阶,最后才正好1阶不剩。...
例如,在图1-1中,根结点A和结点B的度为2,结点C的度为1,叶子结点D,E,F的度为0。所以,该树的度为2。 深度 定义一棵树的根结点所在的层次为1,其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为...
当n=1时,为只有一个根二叉树。 3.排序 (1)冒泡排序 重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列...
9-28 2 二维数组的定义使用 数组排序 9-28 3 顺序查找 二分查找 9-28 4 javascript面向对象编程 9-28 5 javascript对象存在形式 9-28 6 javascript类与对象 9-28 7 给对象指定成员函数 自定义工厂方法 9-30 1 课程...
9-28 2 二维数组的定义使用 数组排序 9-28 3 顺序查找 二分查找 9-28 4 javascript面向对象编程 9-28 5 javascript对象存在形式 9-28 6 javascript类与对象 9-28 7 给对象指定成员函数 自定义工厂方法 9-30 1 课程...
9-28 2 二维数组的定义使用 数组排序 9-28 3 顺序查找 二分查找 9-28 4 javascript面向对象编程 9-28 5 javascript对象存在形式 9-28 6 javascript类与对象 9-28 7 给对象指定成员函数 自定义工厂方法 9-30 1 课程...
注意Wikipedia :插入排序是一种简单的排序算法,它一次创建一个最终排序的数组(或列表),其中一个只有一个。 处理大型列表时,效率要比快速排序,堆排序或合并排序等效率低得多。 时间复杂度 最坏情况O(n ^ 2...
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 3.再对左右区间重复第二步,直到各区间只有一个数。 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部...