C++算法实现:先在一个数组中随机地产生00以内的互不相同的整数。然后使用冒泡排序和快速排序的方法分别对其排序。该怎么处理 - 数据结构与算法当前位置:& &&&C++算法实现:先在一个数组中随机地产生0C++算法实现:先在一个数组中随机地产生00以内的互不相同的整数。然后使用冒泡排序和快速排序的方法分别对其排序。该怎么处理&&网友分享于：&&浏览：540次C++算法实现:先在一个数组中随机地产生00以内的互不相同的整数。然后使用冒泡排序和快速排序的方法分别对其排序。先在一个数组中随机地产生00以内的互不相同的整数。然后使用冒泡排序和快速排序的方法分别对其排序。
1)对每种排序方法分别记录其排序过程中元素的比较次数。
2)比较两种排序方法的优劣。
以上是朋友的数据结构编程题,让我用C++写出算法来,我这望着C++就头痛,都是牛人用的语言,我这菜鸟来的.看看哪位有类似的程序，发上来参考一下吧，谢谢!------解决方案--------------------#include
&iostream&
int data[1000];
void bubble();
void quickSort(int,int);
void main()
bool Flag=
srand((unsigned)time(NULL));
for(int i=0;i &=999;)//产生data[i]
num=rand()%3000+1;
for(int j=0;j &=rem-1;j++)
if(num==data[j])
cout & & &Before sort: & & &
for(int j=0;j &=999;j++)
cout & &data[j] & & &
//quickSort(0,999);
cout & & &After sort: & & &
for(j=0;j &=999;j++)
cout & &data[j] & & &
void bubble()
for(int j=0;j &=999;j++)
for(int i=0;i &=998-j;i++)
if(data[i]& data[i+1])
temp=data[i];
data[i]=data[i+1];
data[i+1]=
int partition(int low,int high)
int current=data[low];
while(low &high)
while((low &high)&&data[high]& =current)
data[low]=data[high];
while((low &high)&&data[low] &=current)
data[high]=data[low];
data[low]=
void quickSort(int low,int high)
if(low &high)
axic=partition(low,high);
quickSort(low,axic-1);
quickSort(axic+1,high);
------解决方案--------------------#include
&stdafx.h &
&stdlib.h&
#define MAX 3000
#define NUM 1000
int * RandInt(int rang, int want)
//rang 范围为1-rang,want为要的数目
int *result = new int[want];
int *r = new int[rang];
for (i = 0; i
r[i] = i+1;
srand((unsigned(time(NULL))));
for (k = rang-1; k &
i = rand()%k;
int temp = r[k];
r[k] = r[i];
for (k = 0; k
result[k] = r[rang-k-1];
delete []r;
int BubbleSort(int a[], int n)
int numCompare = 0;
for (int i = 0; i
bool exchange =
for (int j = n-1; j & j--)
numCompare++;
int temp = a[j];
a[j] = a[j-1];
exchange =
if (!exchange)
return numC
return numC
int Partion(int a[],int i, int j, int & numCompare)
//找中间值
int temp = a[i];
& j && a[j] & = temp)
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有5660人阅读
转载请注明出处：
冒泡排序：
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到不再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。
算法步骤：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。对所有元素在一趟比较之后，最后的元素应该就是最大的数。
3.针对除最后已排好序的所有的元素重复以上步骤1和2，直到没有任何一对数字需要比较。
时间复杂度：
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：C(min) = n-1, M(min) = 0。所以，冒泡排序最好的时间复杂度为：o(n)。
若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：C(max) = n(n-1)/2 = o(n^2) M(max) =&&3n(n-1)/2 = o(n^2)。所以，冒泡排序的最坏时间复杂度：o(n^2)
综上，因此冒泡排序总的平均时间复杂度为：o(n^2)。
空间复杂度：
该算法只有在进行数据交换时最多需要一个临时变量，因此空间复杂度为o(1)。
算法稳定性：
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，则不需要进行交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，因此相同元素的前后顺序不会发生改变，冒泡排序是一种稳定排序算法。
#include &stdio.h&
void Swap(int *a,int *b)
int tmp = *a;
void BubbleSort(int arr[],int len)
/*需要n-1趟排序*/
for (int i = 0; i & len - 1; ++i)
for (int j = 0; j & len -1 - ++j)
if (arr[j] & arr[j+1])
swap(&arr[j],&arr[j+1]);
int main(int argc, char const *argv[])
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i & ++i)
printf(&%d &,arr[i]);
printf(&\n&);
BubbleSort(arr,len);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
直接插入排序：
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序。
算法步骤：
1.从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到下一位置中。
6. 重复步骤2。
时间复杂度：
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上
(n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
空间复杂度：
直接插入排序只有需要一个临时变量存储将要插入的数据，因此空间复杂度为o(1)。
算法稳定性：
直接插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
#include &stdio.h&
void InsertSort(int arr[],int n)
for (int i = 1; i & ++i)
int tmp = arr[i];
for (j = j & 0 && arr[j-1] & --j)
arr[j] = arr[j-1];
int main(int argc, char const *argv[])
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
InsertSort(arr,len);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
希尔排序：
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
算法步骤：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2&d1重复上述的分组和排序，直至所取的增量dt=1(dt&dt-l&…&d2&d1)，即所有记录放在同一组中进行直接插入排序为止。
时间复杂度：
希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^2)，而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4))，但是现今仍然没有人能找出希尔排序的精确下界。
空间复杂度：
希尔排序只有需要一个临时变量存储将要插入的数据，因此空间复杂度为o(1)。
算法稳定性：
由于进行了多次直接插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
#include &stdio.h&
void ShellSort1(int arr[],int n)
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap & 0; gap /= 2)
/*对各组进行排序*/
for (int i = i & ++i)
int tmp = arr[i];
for (j = j &= gap && arr[j - gap] & j -= gap)
arr[j] = arr[j - gap];
void ShellSort2(int arr[],int n)
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap & 0; gap /= 2)
/*对各组进行排序*/
for (int i = i & ++i)
int tmp = arr[i];
for (j = j &= gap && arr[j -gap] & j -= gap)
arr[j] = arr[j - gap];
arr[j -gap] =
int main(int argc, char const *argv[])
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
ShellSort1(arr,len);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
简单选择排序：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。&
算法步骤：
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
1.初始状态：无序区为R[1..n]，有序区为空。
2.第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
3.第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
时间复杂度：
选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。 比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。因此简单选择排序的时间复杂度是O(n^2)。
空间复杂度：
这里需要一个额外的空间存储当前临时的最小值，因此空间复杂度为O(1)。
算法稳定性：
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5
8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
#include &stdio.h&
void swap(int *a,int *b)
int tmp = *a;
void SimpleSelectSort(int arr[],int len)
for (int i = 0; i & ++i)
int min_index =
for (int j = i + 1; j & ++j)
if (arr[j] & arr[min_index])
min_index =
if (min_index != i)
swap(&arr[i],&arr[min_index]);
int main(int argc, char const *argv[])
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
SimpleSelectSort(arr,len);
for (int i = 0; i & ++i)
printf(&%d &, arr[i]);
printf(&\n&);
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。
算法步骤：
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。 （1）用大根堆排序的基本思想 ：
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 。
② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
…… 直到无序区只有一个元素为止。&
（2）大根堆排序算法的基本操作：
&① 初始化操作：将R[1..n]构造为初始堆。
&② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
&①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。&
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
时间复杂度：
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
空间复杂度：
和上面算法一样，堆排序是就地排序，辅助空间为O(1）。
算法稳定性：
堆排序是不稳定的排序方法。
#include &stdio.h&
void swap(int *a,int *b)
int tmp = *a;
/*堆调整*/
void HeapAdjust(int *arr,int i,int size){
int lchild = 2*i+1;
//节点i的左子节点
int rchild = 2*(i+1);
//节点i的右子节点
if (i &= size/2)
//只对非叶节点进行调整
if (lchild & size && arr[lchild] & arr[max])
if (rchild & size && arr[rchild] & arr[max])
if (max != i)
swap(&arr[i],&arr[max]);
HeapAdjust(arr,max,size);//对调整过的max节点重新进行堆调整
/*建立无序大顶堆*/
void BulidHeap(int *arr,int size)
for (int i = size/2; i &= 0; --i)
HeapAdjust(arr,i,size);
/*堆排序*/
void HeapSort(int *arr, int size)
BulidHeap(arr,size);
for (int i = size - 1; i & 0; --i)
swap(&arr[0], &arr[i]);
HeapAdjust(arr,0,i);
int main(int argc, char const *argv[])
int size = 10;
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
for (int i = 0; i & ++i)
printf(&%d &,arr[i]);
printf(&\n&);
HeapSort(arr, size);
for (int i = 0; i & ++i)
printf(&%d &,arr[i]);
printf(&\n&);
归并排序：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列的排序算法。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide
and Conquer）的一个非常典型的应用。它将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法步骤：
归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾。
如 设有数列{6，202，100，301，38，8，1}&
初始状态：[6] [202]
[100] [301] [38] [8] [1] & & &比较次数&
i=1 &&[6 202 ] [ 100 301] [ 8 38] [ 1 ]3
i=2[ 6 100 202 301 ] [ 1 8 38 ]4&
i=3 [ 1 6 8 38 100 202 301 ]4
&总计： 11次
时间复杂度：
将参加排序的初始序列分成长度为1的子序列进行第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列（若n为奇数，还会存在一个最后元素的子序列），再调用排序函数进行第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列， 第 i 趟排序就是两两归并长度为
2^(i-1) 的子序列得到 n / (2^i) 长度为 2^i 的子序列，直到最后只剩一个长度为n的子序列。由此看出，一共需要 log2n 趟排序，每一趟排序的时间复杂度是 O(n), 由此可知 该算法的总的时间复杂度是是 O(n log2n)。
空间复杂度：
归并排序算法需要和原数据规模一样大的辅助空间 ，因此其空间复杂度是 O(n)。
算法稳定性：
归并（Merge）排序法是一个稳定的排序算法。
#include &stdio.h&
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int tmp[10];
void Merge(int begin,int middle,int end)
int j = middle + 1;
while(i &= middle && j &= end)
if (arr[i] &= arr[j] )
tmp[k++] = arr[i++];
tmp[k++] = arr[j++];
while(i &= middle)
tmp[k++] = arr[i++];
while(j &= end)
tmp[k++] = arr[j++];
for (k = k &= ++k)
arr[k] = tmp[k];
void MergeSort(int begin,int end)
if (begin & end)
int middle = (begin + end) / 2;
MergeSort(begin,middle);
MergeSort(middle + 1,end);
Merge(begin,middle,end);
int main(int argc, char const *argv[])
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i & ++i)
printf(&%d &,arr[i] );
printf(&\n&);
MergeSort(0,len - 1);
for (int i = 0; i & ++i)
printf(&%d &,arr[i] );
printf(&\n&);
快速排序：
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法步骤：
一趟快速排序的算法是：
&1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
&2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
&3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换；&
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换；&
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。
待排序的数组A的值分别是：（初始关键数据：key=49） 注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。
进行第一次交换后：27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找，此时:J=6）
进行第二次交换后：27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找&key的值，65&49,两者交换，此时：I=2 )
进行第三次交换后：27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后：27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于key的值，97&49，两者交换，此时：I=3,J=5 )
此时再执行第三和四步的时候就发现i=J=4，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。
时间复杂度：
快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。
空间复杂度：
快速排序需要一个额外的空间存储关键元素（pivot element）,因此空间复杂度为O(1)。
算法稳定性：
快速排序不稳定，且是在关键元素和某个元素发生交换时导致稳定性被破坏，比如序列5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会破坏元素3的稳定性。
#include &stdio.h&
#include &string.h&
#include &malloc.h&
void swap(int *a,int *b)
int partition(int *arr,int low,int high)
int pivot = arr[low];
while(low & high)
while(low & high && arr[high] &= pivot)
if (low & high)
swap(&arr[low],&arr[high]);
while(low & high && arr[low] &= pivot)
if(low & high)
swap(&arr[low],&arr[high]);
void quickSort(int *arr,int low,int high)
if (low & high)
pivotpos = partition(arr,low,high);
quickSort(arr,low,pivotpos-1);
quickSort(arr,pivotpos+1,high);
int main(int argc, char const *argv[])
printf(&please input the length of arr:\n&);
scanf(&%d&,&n);
//int *arr
= (int*)malloc(n * sizeof(int));
int arr[n];
printf(&please input
%d numbers for each elements\n&, n);
for(int i = 0; i & i++)
scanf(&%d&,&arr[i]);
quickSort(arr,0,n-1);
for (int i = 0; i & ++i)
printf(&%d &,arr[i]);
printf(&\n&);
以上就是基本的数据结构排序算法，欢迎补充和讨论。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：100854次
排名：千里之外
原创：14篇
转载：16篇
评论：12条
(1)(2)(2)(3)(1)(10)(1)(4)(6)文章-1208&
trackbacks-0
如何实现类似PHOTOSHOP中的图像任意变形效果，目前GDI+可以轻松实现由长方形变成任意平行四边形，但无法轻意解决变成梯形、三角形和任意四边形。例如下例：扭曲变形效果之一:扭曲变形效果之二:在下一代操作系统Vista中, 图形图像通过WPF的三维映射相应方式可以解决此问题(见我的一篇文章:),但有没有更直接的算法来解决此问题呢?经过搜索,在网上找到一篇论文:
彩色图象的二维变形(作者:向辉)&&& 摘& 要& 该文讨论了彩色图像的变形扭曲技术，并针对二维变形给出了一个速度、精度均令人满意的算法。&&& 关键词& 变形& 反变换& 双线性插值& 增量计算一、引言&　　在图像处理的应用中，一般图像所覆盖区域边界是规则的矩形。为获得某种特殊效果， 常常需要将图像变换到具有任意不规则边界的二维区域或映像到三维空间曲面，简单地说? 是所谓的图像变形技术。本文重点讨论了其中的任意二维多边形区域的变形问题，并针对色图像给出一个切实可行的算法。而三维情况下，则属于计算机图形学中的纹理贴面范围.一般均会牵涉到立体图形消隐、明暗处理等技术，比较复杂，本文未作深入探讨。二、变换原理　　本文所要讨论的二维变形问题可以形式化说明如下:图像定义在矩形区域ABCD之上，源多边形区域P=p1p2…pnp1(Pi为顶点，i=1，2，…n)完全包含在ABCD内；变形就是通过变换f，将P上的图像变换到目的多边形区域Q=Q1Q2…QnQ1(Qi为顶点，i=1，2，…n)，其中，P与Q中的各顶点一一对应，即有:Qi=f(Pi)(i=1,2…n)。图1是变形的一个简单例子:图中的源多边形区域是矩形区域ABCD，目的多边形为任意四边形EFGH，阴影部分在变换前后的变化清楚地说明了变形的效果。@@T5S13200.GIF;图1@@　　那么，变换应该如何进行呢? 一种直接的思路是显式地求出变换f的表达式。而f的实施又分两种方法；其一为正向变换，即用f将P内的任一像素点变换到Q内，取原像素值加以显示。由于P与Q所包含像素点的数目一般不相同，甚至相差很大，造成Q中的像素点或者未被赋值，形成令人讨厌的空洞，或者被多次赋值，浪费了时间，总的效果不理想；其二利用f的反变换f-1，将Q内的每一像素点反变换至P内的对应点，一般此点具有实数坐标，则可以通过插值，确定其像素值，这样，结果图像中的每一像素点均被赋值唯一的一次，既提高了精度，又可以避免不必的赋值，使用效果较好。&　　上述显示求变换(或反变换)的表达式的思路，比较精确，但是这往往牵涉到复杂的多元方程求解问题，并非轻易可以完成。本文所给出的另外一条思路是:既然P与Q中各顶点一一 对应 ，组成变换对，即源多边形P中的任一顶点Pi(i=1,2…n)经过变换f，得到目的多边形Q中的顶点Qi(i=1,2…n)，则Qi的反变换点也必为Pi。这样，对Q内(包括边界)的各像素点A，可以利用各顶点的反变换点的坐标值通过双线性插值技术近似求出其反变换点B；用点B的坐标值在源图像中进行插值，最终求得结果像素值，用于显示A。&　　第二种方法在保留一定精度的前提下，避免了变换表达式的显式求解，实现简便。本文基于此思想，设计了一个快速变形算法；另外，算法中还借鉴了多边形区域扫描转换的扫法的思路，以实现对Q内各像素点的高效扫描。以下，本文首先介绍了插值技术及增量计算技术，然后将给出二维变形算法的详细步骤。三、插值技术　　已知目的多边形Q各顶点Qi(i=1,2…n)的变换坐标值，如何求出Q内任一像素的反变换坐标呢?双线性插值法是一种简单快速的近似方法。具体做法是:先用多边形顶点Qi(i=1,2)的反变换坐标线性插值出当前扫描线与多边形各边的交点的反变换坐标，然后再用交点的 反变换坐标线性插值出扫描线位于多边形内的区段上每一像素处的反变换坐标值用于以 后的计算。逐条扫描线处理完毕后，Q内每一像素点的反变换坐标值也就均求出来了。如图 2中所示，扫描线Y(纵坐标=Y)与多边形相交于点A和B两点，D则是位于扫描线上位于多边形的区段AB上的任一点。已知多边形的3个顶点Qi(i=1,2，3)的反变换坐标为(RXi,RYi)； 又令A、B及D各点的反变换坐标分别是(RXa,RYa),(RXb,RYb)和(RXd,RYd)。则RXp可按以下??式求出:　　RXa=uRX1+(1-u)RX2&&& 式1　　RXb=vRX1+(1-v)RX3式2　　RXd=tRXa+(1-t)RXb 式3　　其中，u=|AQ2|/|Q1Q2|，v=|BQ3|/|Q1Q3|，t=|DB|/|AB|，称为插值参数。　　RYd的值亦可完全类似地求出，甚至不必改变插值参数的计算。(Rxd,Ryd)即是D点在原图像中对应点的坐标近似值。@@T5S13201.GIF;图2@@&　　上述的双线性插值过程可以通过增量计算方法提高速度。其中，在水平方向上，位于多边形内的各区段上的各像素的反变换坐标可以沿扫描线从左至右递增计算。仍以反变换的X 坐标 为例。如图2所示，在扫描线Y上，C与D是相邻两像素点，对C点，插值参数tc=|CB|/| AB|，对D点，td=|DB|/|AB|，则插值参数之差△t=|CD|/|AB|，由于C与D相邻， 且在同一扫描线上，|CD|=1，即△t=1/|AB|，在AB区段上为常数。根据式1～式3，不难 推得D点的反变换X坐标Rxd与C点的反变换X坐标Rxc之间的关系如下:　　Rxd=Rxc+(Rxa-Rxb)·△t=Rxc+△Rxx&由于△Rxx在AB区段仍为常数，故AB区段上各像素点的反变换X坐标均可由A点的Rxa依次递? 求得，而反变换Y坐标的递增求法亦是相同。这样，AB区段上各像素点的反变换坐标值的计 算简化为两次加法，时间的节省是惊人的。事实上，在垂直方向，每条边也可在相邻扫描??间递增计算其与扫描线交点的反变换坐标。如图2中的Q1Q2边，其与相邻的两条扫描线Y 与Y-1分别交于A点和E点。则两点的插值参数之差△u=|AE|/|Q1Q2|，而Q1Q2边 与扫描线交角固定为θ，且A和E两点的Y坐标之差为1，则有:|AE|=1/Sinθ，对于Q1Q 2边而言是常量，因此△u对此边也是常量，于是推得两点反变换X坐标关系如下:　　Rxa=Rxe+(Rx1-Rx2)△u=Rxe+△Rxy　　显然，△Rxy沿Q1Q2边亦是常数，故而可知，相邻扫描线与各边交点的反变换坐标也只 要两次浮点加法的计算量。这样，区域内每一像素点的反变换均可通过增量计算高效地完，这大大提高了整个变形算法的速度。&另外，前面提到，经过反变换后的点一般具有实数坐标，无法直接在原图像中获得颜色值。但我们知道，一幅所谓数字图像，其实质是对连续图像在整数坐标网格点上的离散采????而可以用插值的方法，得到区域内具有任意坐标的点的颜色值。插值即是对任意坐标点的? 色值，用其周围的若干像素(具有整值坐标值，颜色值确定)的颜色值按一定插值公式近似? 算。一般有最近邻点法、双线性插值法及3次样条函数法等插值方法，出于精度与速度的折 衷要求，选用双线性插值方 法对绝大多数的应用场合是适宜的。需特别指出的是，应该对 颜色的3原色分量分别进行插值，而不要直接使用读像素点得到的颜色索引号。详细讨论见 文献[1]。四、算法细节&　　下面将要给出的彩色图像的二维变形算法以多边形区域扫描转化的扫描线算法为框架， 且使用相仿的数据结构，对目的多边形区域高效地进行逐点扫描，同时实现前面讨论的各? 旨际酢?&&& 首先给出的是用C语言描述的数据结构:struct Edge{&&&&&&&&&&&&&& /*在边的分类表ET中表示边的下端点的x坐标；在边的活化链表AEL中则表示边与扫描线的交点的x坐标；*/&&&&&&&&&&&& /*边的斜率的倒数；即沿扫描线间方向X的增量值*/&&& int Y&&&&&&&&& /*边的上端点的y坐标*/&&& float Rx;&&&&&&&&& /*在ET中表示边的下端点*/&&& float Ry;&&&&&&&&& /*的反变换坐标；在AEL中则表示边与扫描线交点的反变换坐标*/&&&&float dRx;&&&&&&&& /*沿扫描线间方向，反变*/&&&&float dRy;&&&&&&&& /*换坐标(Rx,Ry)的增量值*/&&&&struct Edge * /*指向下一条边的指针*/}; /*多边形的边的信息*/struct Edge *ET[YResolution];/*边的分类表，按边的下端点的纵坐标Y对非水平边进行分类的指针数组。下端点的Y值等于i的边归入第i类，同一类中，各边按X值及△X的值递增顺序排列；YResolution为扫描线数目*/struct Edye *AEL;/*边的活化链表，由与当前扫描线相交的所有多边形的边组成，记录了多边形边沿当前扫描线的交点序列。*/struct Polygon{&&&&&&&&&&&&& /*多边形顶点数*/&&& struct Point *P& /*多边形的顶点序列*/}; /*多边形信息*/struct Point {&&& int X;&&& int Y;&&&&&& /*顶点坐标*/&&& float Rx;&&& float Ry;&&& /*顶点的反变换坐标*/}; /*多边形各顶点的信息*/　　注意以上注释中边的下端点指纵坐标值较小的一端，另一端即为上端点。　　以下则为算法的详细步骤:　　　　1.数据准备　　　　　对于每一条非水平边QiQi+1，设Qi与Qi+1的坐标分别为(Xi,Yi)及(Xi+1,Yi+1)；其反变换坐标为(Rxi,Ryi)及(RXi+1,RYi+1)。　　　　　则按以下各式对此边的信息结构各域进行填写:　　　　　X=Xi,Yi＜Yi+1　　　　　Xi+1,Yi＞Yi+1　　　　　RX=RXi,Yi＜Yi+1　　　　　RXi+1,Yi＞Yi+1　　　　　RY=RYi,Yi＜Yi+1　　　　　RYi+1,Yi＞Yi+1　　　　　dx=(xi-xi+1)/(yi-yi+1)　　　　　Ymax=max(yi，yi+1)　　　　　dRx=(Rxi-Rxi+1)/(yi-yi+1)　　　　　dRy=(Ryi-Ryi+1)/(yi-yi+1)　　　　　然后将其插入链表ET[min(yi，yi+1)]中。活化边表AEL置空。　　　　　当前扫描线纵坐标y取为0，即最小序号。　　　　2.扫描转换　　　　　　反复作以下各步，直到y等于YResolution　　　　　　(1)若ET[y]非空，则将其内所有边插入AEL。　　　　　　(2)若AEL非空，则将其按X及dx的值从小到大排列各边，接(3)；否则转　　　　　　(3)将AEL内各边按排列顺序两两依次配对。则沿当前扫描线Y组成若干水平区间[xLeft,xRight]，其左右端点的反变换坐标分别为:(lRx,lRy)，(rRx,rRy)。则对于每一个这样的区间作以下各步:　　　　　　　dRxx=(lRx-rRx)/(xleft-xRight)　　　　　　　dRyx=(lRy-rRy)/(xleft-xRight)　　　　　　又设原图像已读入二维数组Image之中。令XX=xleft, Rxy=lRx, Ryx=lRy则对于每个满足xLeft≤xX≤xRight的坐标为(xx,y)的像素，其反变换坐标(Rxy,Ryx)可按下式增量计算:　　　　　　　Rxx=Rxx+dRxx　　　　　　　Ryx=Ryx+dRyy　　　　　　用(Rxx,Ryx)在数组Image之中插值，(参见文献[1])，按所得颜色值显示该像素。然后边x=x+1，计算下一像素。　　　　　　(4)将AEL中满足y=Ymax的边删去，然后按下式调整AEL中各边的信息。　　　　　　　X=X+dx　　　　　　　Rx=Ry+dRx　　　　　　　Ry=Ry+dRy　　　　　　(5)y=y+1,重复下一点。五、讨论&　　上述算法针对彩色图像的二维变形问题，给出了一个简单快速的实现方案。至于三维变形，由于一般会牵涉到隐藏面消除等问题，比较复杂。但在一些情况下，可以避开消隐问? 目的曲面形状比较简单，投影到屏幕后，各部分均不发生重叠，也就没有必要使用消隐技术，直接投影就可以了。这时就仍然可以利用本文介绍的二维变形技术，进行处理。方法是: 将曲面用许多小平面多边形进行逼近，再将各个小多边形投影到屏幕上，形成二维多边形? 在确定了小多边形到原图像各部分的对应关系之后，三维问题就转化成了二维问题，速度较快，也能达到一定的效果。若掌握了消隐技术之后，则可以处理任意的曲面变形了，思路同上。参考文献[1]向辉 寿标“真实感图像的颜色插值及其应用”，计算机世界月刊，1992年10月
发表于 @ ||引文来源&&
阅读(...) 评论() &