Given an array withnobjects colored red, white or blue,sort them so that objects of the same color are adjacent, with the colors inthe order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red,white, and blue respectively.
Note:You are not suppose to use the library’s sort function for this problem.
click to show follow up.
HideTags
ArrayTwo PointersSort
#pragma once#include<iostream>#include<vector>using namespace std;//法1：参数为 数组和数组大小 的快速排序void sortColors(int A[], int n){if (n <= 1){cout << "return" << endl;return;}int pivot = A[0];int begain = 0;int end = n – 1;while (begain < end){while (A[end] >= pivot && end > begain)end–;A[begain] = A[end];while (A[begain] <= pivot&&begain < end)begain++;A[end] = A[begain];}A[begain] = pivot;sortColors(A, begain);sortColors(A + begain + 1, n – begain – 1);}//法2：线性扫描，，统计次数，重新赋值void sortColors2(int A[], int n){int colors[] = { 0, 0, 0 };for (int i = 0; i < n; i++)colors[A[i]]++;int index = 0;for (int i = 0; i < 3; i++)for (int j = 0; j < colors[i]; j++)A[index++] = i;}void main(){int A[] = { 1, 2, 2, 2, 2, 0, 0, 0, 1, 1 };sortColors2(A, 10);for (int i = 0; i < 10; i++)cout << A[i] << ' ';cout << endl;system("pause");}
只要笑一笑，没什么事请过不了
