计算机视觉
图像处理

经典排序算法

经典排序算法——冒泡排序

对于一个int数组,请编写一个冒泡排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例:
输入数组:[1,2,3,5,2,3],6
输出数组:[1,2,2,3,3,5]
  1. class BubbleSort {
  2. public:
  3.     int* bubbleSort(int* A, int n) {
  4.         // write code here
  5.         bool flag=true;
  6.         for(int i=0;i<n && flag;++i)
  7.         {
  8.             for(int j=n-1;j>i;–j)
  9.             {
  10.                 if(A[j]<A[j-1])
  11.                 {
  12.                     int temp=A[j];
  13.                     A[j]=A[j-1];
  14.                     A[j-1]=temp;
  15.                     flag=true;
  16.                 }
  17.             }
  18.         }
  19.         return A;
  20.     }
  21. };

经典排序算法——插入排序

对于一个int数组,请编写一个插入排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例:
输入数组:[1,2,3,5,2,3],6
输出数组:[1,2,2,3,3,5]
  1. class InsertionSort {
  2. public:
  3.     int* insertionSort(int* A, int n) {
  4.         // write code here
  5.         for(int i=1;i<n;++i)
  6.         {
  7.             int insertNum=A[i];//待插入元素
  8.             int j=i;
  9.             while(j>0 && A[j-1]>insertNum)//寻找插入位置
  10.             {
  11.                     A[j]=A[j-1];
  12.                     j–;
  13.             }
  14.             A[j]=insertNum;
  15.         }
  16.         return A;
  17.     }
  18. };

经典排序算法——选择排序

对于一个int数组,请编写一个选择排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例:
[1,2,3,5,2,3],6

[1,2,2,3,3,5]

  1. class SelectionSort {
  2. public:
  3.     int* selectionSort(int* A, int n){
  4.         // write code here
  5.         int k=0;
  6.         for(int i=0;i<n;++i)
  7.         {
  8.            k=i;
  9.            for(int j=i+1;j<n;++j)//找到最小元素
  10.            {
  11.                if(A[j]<A[k])  k=j;
  12.            }
  13.            int temp=A[i];//将最小元素放入i位置
  14.            A[i]=A[k];
  15.            A[k]=temp;
  16.         }
  17.         return A;
  18.     }
  19. };

经典排序算法——快速排序

对于一个int数组,请编写一个快速排序算法,对数组元素排序。

给定一个int数组A及数组的大小n,请返回排序后的数组。

测试样例:
[1,2,3,5,2,3],6

[1,2,2,3,3,5]

  1. class QuickSort {
  2. public:
  3.     int* quickSort(int* A, int n) {
  4.         // write code here
  5.         if(A==NULL || n<2)
  6.             return A;
  7.         process(A,0,n-1);
  8.         return A;
  9.     }
  10.     int* process(int* A, int low,int high) {
  11.         if (low < high) {
  12.             int mid = partition(A, low, high);
  13.             process(A, low, mid-1);//对A[low…mid-1]进行递归操作排序
  14.             process(A, mid + 1, high);//对A[mid+1…high]进行递归操作排序
  15.         }
  16.         return A;
  17.     }
  18.     int partition(int* A,int low,int high){ //快排算法的划分过程,将数组划分为左右两个子数组
  19.         int pivot = A[low];
  20.         int i = low;
  21.         int j = high;
  22.         if (low < high)
  23.         {
  24.             while (i < j)
  25.             {
  26.                 while (i < j && pivot <= A[j])  j–;//找到比基准数小的元素
  27.                 if (i < j)  A[i] = A[j];
  28.                 while (i < j && pivot >= A[i])  i++;//找到比基准数大的元素
  29.                 if (i < j)  A[j] = A[i];
  30.             }
  31.             A[i] = pivot;
  32.         }
  33.         return i;
  34.     }
  35. };

转载注明来源:CV视觉网 » 经典排序算法

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 4

评论前必须登录!