学习笔记【8月8日】

问题：怎么实现堆排序？

#include <bits/stdc++.h>
using namespace std;
void adjustDown(int A[], int k, int len) {
    A[0] = A[k];
for(int i = 2*k; i <= len; i *= 2) {
if(i < len && A[i] < A[i+1]) {
            i++;
        }
if(A[0] >= A[i]) break;
else {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

void buildMaxHeap(int A[], int len) {
for(int i = len/2; i > 0; i--) {
        adjustDown(A, i, len);
    }
}

void heapSort(int A[], int len) {
    buildMaxHeap(A, len);
for(int i = len; i > 1; i--) {
        swap(A[i], A[1]);
        adjustDown(A, 1, i-1);
    }
}

int main()
{
int arr[] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
int len = sizeof(arr)/sizeof(int);
    heapSort(arr, len);
for(int i = 1; i <= len; i++) {
cout << arr[i] << " ";
    }
cout << endl;
return 0;
}

问题：归并排序？
求一个数组中逆序对的个数？

#include <iostream>
using namespace std;
/**
数据范围在[low, high)左闭右开
cnt用于统计数组中逆序对的个数
**/
void merge_sort(int *A, int low, int high, int *T, int &cnt) {
if(high-low > 1) {
int mid = low + (high-low)/2;
int left = low;
int right = mid;
int index = low;
        merge_sort(A, low, mid, T, cnt);
        merge_sort(A, mid, high, T, cnt);
//合并过程
while(left < mid || right < high) {
if(right >= high || (left < mid && A[left] <= A[right])) {
                T[index++] = A[left++];
            } else {
                T[index++] = A[right++];
//相对归并排序添加的内容
                cnt += mid - left;
            }
        }
//复制
for(index = low; index < high; index++) {
            A[index] = T[index];
        }
    }
}


int main()
{
int arr[] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
int len = sizeof(arr)/sizeof(int);
cout << len << endl;
int *tmpArray = new int[len];
int cnt = 0;//逆序对的个数
    merge_sort(arr, 0, len, tmpArray, cnt);
for(int i = 0; i < len; i++) {
cout << arr[i] << " ";
    }
cout << endl;
cout << "逆序对个数： " << cnt << endl;

return 0;
}

归并排序方法一：

#include <iostream>

using namespace std;

/**
数据范围在[low, high)左闭右开
**/
void merge_sort(int *A, int low, int high, int *T) {
if(high-low > 1) {
int mid = low + (high-low)/2;
int left = low;
int right = mid;
int index = low;
        merge_sort(A, low, mid, T);
        merge_sort(A, mid, high, T);
//合并过程
while(left < mid || right < high) {
if(right >= high || (left < mid && A[left] < A[right])) {
                T[index++] = A[left++];
            } else {
                T[index++] = A[right++];
            }
        }
//复制
for(index = low; index < high; index++) {
            A[index] = T[index];
        }
    }
}


int main()
{
int arr[] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
int len = sizeof(arr)/sizeof(int);
cout << len << endl;
int *tmpArray = new int[len];
    merge_sort(arr, 0, len, tmpArray);
for(int i = 0; i < len; i++) {
cout << arr[i] << " ";
    }
cout << endl;
return 0;
}

归并排序方法二：

#include <bits/stdc++.h>

using namespace std;
/**
T 为临时数组,数组范围[low, hight]
**/
void mergesort(int *A, int low, int hight, int *T) {
if(low < hight) {
int mid = low + (hight-low)/2;
        mergesort(A, low, mid, T);
        mergesort(A, mid+1, hight, T);
for(int k = low; k <= hight; k++) {
            T[k] = A[k];
        }
int i = low;
int j = mid + 1;
int index;
for(index = low; i <= mid && j <= hight; index++) {
if(T[i] <= T[j]) {
                A[index] = T[i++];
            } else {
                A[index] = T[j++];
            }
        }
while(i <= mid) A[index++] = T[i++];
while(j <= hight) A[index++] = T[j++];
    }
}

bool MergeSort(int A[], int n) {
int *tmpArray = new int[n];
if(tmpArray == nullptr) {
return false;
    }
    mergesort(A, 0, n-1, tmpArray);
delete []tmpArray;
return true;
}


int main()
{
int arr[] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
int len = sizeof(arr)/sizeof(int);
cout << len << endl;
bool res = MergeSort(arr, len);
for(int i = 0; i < len; i++) {
cout << arr[i] << " ";
    }
cout << endl;
return 0;
}

问题：快速排序？

import java.util.Arrays;
import java.util.Scanner;

public class QuickSortDemo {
public static void quickSort(int A[], int low, int high) {
if(low < high) {
int pivotPos = partition(A, low, high);
            quickSort(A, low, pivotPos-1);
            quickSort(A, pivotPos+1, high);
        }
    }
public static int partition(int A[], int low, int high) {
int pivot = A[low];
while(low < high) {
while(low < high && A[high] >= pivot)--high;
            A[low] = A[high];
while(low < high && A[low] <= pivot)++low;
            A[high] = A[low];
        }
        A[low] = pivot;
return low;
    }
//手动输入测试数据 
public static void testByHand() {
        Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int arr[] = new int[n];
int index = 0;
for(int i = 0; i < n; i++) {
int read = scanner.nextInt();
            arr[index++] = read;
        }
        quickSort(arr, 0, n-1);
        System.out.println(Arrays.toString(arr));
    }
//自动生成测试数据
public static int[] generateRondomArray() {
int[] res = new int[(int) (Math.random() * 20) + 1];
for (int i = 0; i < res.length; i++) {
            res[i] = (int) (Math.random() * 20) + 1;
        }
return res;
    }
public static void main(String[] args) {
int n = 10;
//测试
while(n != 0) {
            n--;
int[] arr = generateRondomArray();
            quickSort(arr, 0, arr.length-1);
            System.out.println(Arrays.toString(arr));
        }
    }
}

问题：求数组中最小的K个数或者求第K小的数？
Java代码

import java.util.Arrays;
public class KthNum {
public static int kth_elem(int a[], int low, int high, int k)
    {
int pivot = a[low];
int low_temp = low;
int hight_temp = high;
while(low < high) {
while(low < high && a[high]>= pivot) --high;
            a[low] = a[high];
while(low < high && a[low]<= pivot) ++low;
            a[high] = a[low];
        }
        a[low] = pivot;
if(low+1 == k) {
return a[low];
        } else if(low+1 > k) {
return kth_elem(a, low_temp ,low-1 , k);
        } else {
//a[]从下标0开始
return kth_elem(a, low+1, hight_temp, k); 
        }
    }
/**
 * 随机生成数组
 */
public static int[] generateRondomArray() {
int[] res = new int[(int) (Math.random() * 20) + 4];
for (int i = 0; i < res.length; i++) {
            res[i] = (int) (Math.random() * 20) + 1;
        }
return res;
    }
/**
 * 在0到end间找一个随机数。
 */
public static int getRanomNumber(int end) {
int start = 0;
int num = (int)(Math.random()*(end-start))+1;
return num%end+1;
    }
public static void main(String[] args) {
//测试的次数
int n = 1000;
while(n != 0) {
            n--;
int arr[] = generateRondomArray();
            System.out.println("array: " + Arrays.toString(arr));
int k = getRanomNumber(arr.length);
int kth = kth_elem(arr, 0, arr.length-1, k);
            Arrays.sort(arr);
            System.out.println("k = " + k + " " + "result of kth num: " + kth + " real kthNumber: " + arr[k-1]);
            System.out.println("afterSorted: " + Arrays.toString(arr));
if(kth == arr[k-1]) {
                System.out.println("Yes !!!!!!!!!!!!");
                System.out.println("\n");
            } else {
                System.out.println("No 5555555555555555");
break;
            }
        }
    }
}

剑指offer C++代码

#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <exception>
#include <set>
#include <vector>
#include <cstdio>
using namespace std;

// Random Partition
int RandomInRange(int min, int max)
{
int random = rand() % (max - min + 1) + min;
return random;
}

void Swap(int* num1, int* num2)
{
int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

int Partition(int data[], int length, int start, int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length) {
// throw new std::exception("Invalid Parameters");
return 0;
    }
int index = RandomInRange(start, end);
    Swap(&data[index], &data[end]);

int small = start - 1;
for(index = start; index < end; ++ index)
    {
if(data[index] < data[end])
        {
            ++ small;
if(small != index)
                Swap(&data[index], &data[small]);
        }
    }

    ++ small;
    Swap(&data[small], &data[end]);
return small;
}


void GetLeastNumbers_Solution1(int* input, int n, int* output, int k)
{
if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
return;

int start = 0;
int end = n - 1;
int index = Partition(input, n, start, end);
while(index != k - 1)
    {
if(index > k - 1)
        {
            end = index - 1;
            index = Partition(input, n, start, end);
        }
else
        {
            start = index + 1;
            index = Partition(input, n, start, end);
        }
    }
for(int i = 0; i < k; ++i)
        output[i] = input[i];
}

// ====================方法2====================
typedef multiset<int, greater<int> >            intSet;
typedef multiset<int, greater<int> >::iterator  setIterator;

void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
{
    leastNumbers.clear();

if(k < 1 || data.size() < k)
return;

vector<int>::const_iterator iter = data.begin();
for(; iter != data.end(); ++ iter)
    {
if((leastNumbers.size()) < k)
            leastNumbers.insert(*iter);

else
        {
            setIterator iterGreatest = leastNumbers.begin();

if(*iter < *(leastNumbers.begin()))
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

// ====================测试代码====================
void Test(char* testName, int* data, int n, int* expectedResult, int k)
{
if(testName != NULL)
printf("%s begins: \n", testName);

vector<int> vectorData;
for(int i = 0; i < n; ++ i)
        vectorData.push_back(data[i]);

if(expectedResult == NULL)
printf("The input is invalid, we don't expect any result.\n");
else
    {
printf("Expected result: \n");
for(int i = 0; i < k; ++ i)
printf("%d\t", expectedResult[i]);
printf("\n");
    }

printf("Result for solution1:\n");
int* output = new int[k];
    GetLeastNumbers_Solution1(data, n, output, k);
if(expectedResult != NULL)
    {
for(int i = 0; i < k; ++ i)
printf("%d\t", output[i]);
printf("\n");
    }

delete[] output;

printf("Result for solution2:\n");
    intSet leastNumbers;
    GetLeastNumbers_Solution2(vectorData, leastNumbers, k);
printf("The actual output numbers are:\n");
for(setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
printf("%d\t", *iter);
printf("\n\n");
}

// k小于数组的长度
void Test1()
{
int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
int expected[] = {1, 2, 3, 4};
    Test("Test1", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k等于数组的长度
void Test2()
{
int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
int expected[] = {1, 2, 3, 4, 5, 6, 7, 8};
    Test("Test2", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k大于数组的长度
void Test3()
{
int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
int* expected = NULL;
    Test("Test3", data, sizeof(data) / sizeof(int), expected, 10);
}

// k等于1
void Test4()
{
int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
int expected[] = {1};
    Test("Test4", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// k等于0
void Test5()
{
int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
int* expected = NULL;
    Test("Test5", data, sizeof(data) / sizeof(int), expected, 0);
}

// 数组中有相同的数字
void Test6()
{
int data[] = {4, 5, 1, 6, 2, 7, 2, 8};
int expected[] = {1, 2};
    Test("Test6", data, sizeof(data) / sizeof(int), expected, sizeof(expected) / sizeof(int));
}

// 输入空指针
void Test7()
{
int* expected = NULL;
    Test("Test7", NULL, 0, expected, 0);
}

int main(int argc, char* argv[])
{
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    Test7();
return 0;
}

此题可以作为学习状态压缩的入门题目：
同类题目：hdu：拯救大兵瑞恩
参考博客

参考牛客网大神的C++代码， 之前状态压缩很少接触，只了解在动态规划中用的比较多。

#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int N = 110;
char mz[N][N];
bool vis[N][N][N*10];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int m, n;
map<char, int> key;

struct node {
int x, y, cnt, state;
    node():cnt(0), state(0) {}
};
queue<node> que;

int bfs(int sx, int sy, int ex, int ey) {

while(!que.empty()) que.pop();
    node tmp;
    tmp.x = sx, tmp.y = sy;
    que.push(tmp);

while(!que.empty()) {
        node p = que.front();
if(p.x == ex && p.y == ey) {
return p.cnt;
        }
        que.pop();

for(int i = 0; i < 4; ++i) {
int newx = p.x + dx[i];
int newy = p.y + dy[i];
//检查边界
if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue;
//遇到墙
if(mz[newx][newy] == '0') continue;

int state = p.state;
//小写字母对应大写字母的钥匙
if(mz[p.x][p.y] >= 'a' && mz[p.x][p.y] <= 'z') {
                state |= (1<<key[mz[p.x][p.y]]);
            }
//访问过.
if(vis[newx][newy][state]) continue;
//如果遇到门，判断是否有门上的钥匙
if(mz[newx][newy] >= 'A' && mz[newx][newy] <= 'Z') {
//转为对应的小写字母，然后再map中取映射的数字.
char ch = mz[newx][newy] - 'A' + 'a';
if((state & (1 << key[ch])) == 0) {
continue;
                }
            }
/**
 如果持有的钥匙是一样的，也就是state相等，
 那么第一次访问是最短的,所以标记访问过
 以后不在访问
 **/
            vis[newx][newy][state] = true;
            tmp.x = newx;
            tmp.y = newy;
            tmp.cnt = p.cnt + 1;
            tmp.state = state;
            que.push(tmp);
        }
    }
return -1;
}

int main() {
while(scanf("%d%d", &m, &n) != EOF) {
int sx, sy, ex, ey;
int cnt = 0;
for(int i = 0; i < m; ++i) {
scanf("%s", mz[i]);
for(int j = 0; j < n; ++j) {
if(mz[i][j] == '2') {
                    sx = i, sy = j;
                }
if(mz[i][j] == '3') {
                    ex = i, ey = j;
                }
if(mz[i][j] >= 'a' && mz[i][j] <= 'z') {
                    key[mz[i][j]] = cnt++;
                }
            }
        }
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
for(int s = 0; s < (1<<cnt); ++s) {
                    vis[i][j][s] = false;
                }
            }
        }
int Ans = bfs(sx, sy, ex, ey);
printf("%d\n", Ans);
    }
return 0;
}
/**
5 5
02111
01a0A
01003
01001
01111
**/

Java实现，但是效率不高。

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
// 四个方向
private static int[] xx = new int[] { 0, 0, 1, -1 };
private static int[] yy = new int[] { 1, -1, 0, 0 };

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int m = scanner.nextInt();//row
int n = scanner.nextInt();//col
            scanner.nextLine();

char[][] datas = new char[m][n];
for (int i = 0; i < m; i++) {
                datas[i] = scanner.nextLine().toCharArray();
            }

int x0 = 0, y0 = 0;
int xd = 0, yd = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
//出发地
if (datas[i][j] == '2') {
                        x0 = i;
                        y0 = j;
continue;
                    }
//目的地
if (datas[i][j] == '3') {
                        xd = i;
                        yd = j;
break;
                    }
                }
            }
            System.out.println(bfs(datas, m, n, x0, y0, xd, yd));
        }

    }

private static int bfs(char[][] datas, int m, int n, int x0, int y0, int xd, int yd) {
        LinkedList<Node> queue = new LinkedList<>();
int[][][] keys = new int[m][n][1024];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int s = 0; s < 1024; s++) {
                    keys[i][j][s] = Integer.MAX_VALUE;
                }
            }
        }

        queue.add(new Node(x0, y0, 0));
        keys[x0][y0][0] = 0;

        Node node = null;
int x = 0;
int y = 0;
int key = 0;

while (queue.size() > 0) {
            node = queue.poll();
            x = node.x;
            y = node.y;
            key = node.key;
//到达出口
if (x == xd && y == yd) {
return keys[x][y][key];
            }

for (int i = 0; i < 4; i++) {
                x = node.x + xx[i];
                y = node.y + yy[i];
                key = node.key;
//检查边界
if (!isValid(x, y, m, n, datas)) {
continue;
                }
// 最多10把钥匙
if (datas[x][y] >= 'a' && datas[x][y] <= 'j') {
                    key = key | (0x1 << (datas[x][y] - 'a'));
                }
// 有对应的钥匙继续往下走，没有则跳过
if (datas[x][y] >= 'A' && datas[x][y] <= 'J') {// door
if ((key & (0x1 << (datas[x][y] - 'A'))) > 0) {// haskey
// key = key | ~(0x1 << (datas[x][y] - 'A'));
                    } else {
continue;
                    }
                }
/**
 * 1. keys[x][y][key] > keys[node.x][node.y][node.key] + 1 
 * 表示如果之前keys[x][y][key]没有走过， 则是Integer.MAX_VALUE， 表示需要这么多步才被到达。
 * 2.如果keys[x][y][key]之前已经走过，但是路径走的步数比keys[node.x][node.y][node.key] + 1大，说明有到这里有更近的路， 应该被更新。
 * 3.如果key刚刚被更新， 也就是新添加了钥匙， 说明这是（带着新增加的钥匙）第一次走， 应该被更新.
 * 
 */
if (keys[x][y][key] > keys[node.x][node.y][node.key] + 1) {
                    keys[x][y][key] = keys[node.x][node.y][node.key] + 1;
                    queue.add(new Node(x, y, key));
                }

            }
        }
return Integer.MAX_VALUE;
    }

private static boolean isValid(int x, int y, int m, int n, char[][] data) {
if (x >= 0 && x < m && y >= 0 && y < n && data[x][y] != '0') {
return true;
        }
return false;
    }

private static class Node {
int x;
int y;
int key;

public Node(int x, int y, int keys) {
this.x = x;
this.y = y;
this.key = keys;
        }
    }
}
/**
5 5
02111
01a0A
01003
01001
01111
**/

1。判断两个字符串是否互为旋转词？
2。判断两个字符串是否互为变形词？

public class Deformation {
/**
 * 
 * 题目：给定两个字符串str1和str2， 如果str1和 str2中出现的字符种类数一样且每种字符出现的次数也一样，那么str1和str2互为变形词
 * 现在给两个字符串，判断两则是否为变形词。
 * @param str1 字符串
 * @param str2 字符串
 * @return true or false
 * 如果字符的种类很多， 可以用哈希表代替长度为256的数组。
 */
public static boolean isDeformation(String str1, String str2) {
if(str1 == null || str2 == null || str1.length() != str2.length()) {
return false;
        }
char []strA = str1.toCharArray();
char []strB = str2.toCharArray();
int []map = new int[256];
for(int i = 0; i < strA.length; i++) {
            map[strA[i]]++;
        }
for(int i = 0; i < strB.length; i++) {
if(map[strB[i]]-- == 0) {
return false;
            }
        }
return true;
    }

/**
 * 题目：如果把一个字符str， 把字符串str前面任意部分挪到后面形成的字符串叫作str的旋转词
 * 比如：str="12345"的旋转词有 "12345", "23451", "34512", "45123", "51234"
 * 给定两个字符串a和b， 请判断a和b是否互为旋转词.
 * 思路：连接两个a，然后判断是否包含b， 因为连接两个a穷举了所有的旋转词。
 * @param a 
 * @param b
 * @return
 */
public static boolean isRotation(String a, String b) {
if(a == null || b == null || a.length() != b.length()) {
return false;
        }
        String b2 = b+b;
return getIndexOf(b2, a) != -1;//KMP
    }
public static int getIndexOf(String s, String m) {
if(s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
        }
char []ss = s.toCharArray();
char []ms = m.toCharArray();
int si = 0;
int mi = 0;
int [] next = getNextArray(ms);
while(si < ss.length && mi < ms.length) {
if(ss[si] == ms[mi]) {
                si++;
                mi++;
            } else if(next[mi] == -1) {
                si++;
            } else {
                mi = next[mi];
            }
        }
return mi == ms.length ? si - mi : -1;
    }
public static int[] getNextArray(char[] ms) {
if(ms.length == 1) {
return new int[]{-1};
        }
int [] next  = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
int pos = 2;
int cn = 0;
while(pos < next.length) {
if(ms[pos-1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if(cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
return next;
    }
public static void main(String[] args) {
        String a1 = "cdab", b1 = "abcd";
        String a2 = "1ab2", b2 = "ab12";
        String a3 = "2ab1", b3 = "ab12";
        System.out.println(isRotation(a1, b1));
        System.out.println(isRotation(a2, b2));
        System.out.println(isRotation(a3, b3));
    }
}

C++系统提供的排序函数：
转载链接

//参考 http://www.cplusplus.com/reference/algorithm/sort/
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

/**
模板方法
**/
template <typename T>
void Print (vector<T> arr) {
int Size = arr.size();
cout << "size: " << Size << " ";
for (int i = 0; i < Size; ++i){
cout << arr[i] << " ";
      }
cout << endl;
}

bool CompIntLess(int first,int second){
return first < second;
}

bool CompIntGreater(int first,int second){
return first > second;
}
//对容器vector排序
void SortInt()
{
vector<int> arr;
  arr.push_back(4);
  arr.push_back(5);
  arr.push_back(1);
  arr.push_back(2);

//排序
cout << "sort with from small to big: " << endl;
  sort(arr.begin(),arr.end(),less<int>());
  Print(arr);

cout << "sort with from big to small: " << endl;
  sort(arr.begin(),arr.end(),greater<int>());
  Print(arr);

//稳定排序
cout << "sort with from small to big" << endl;
  stable_sort(arr.begin(),arr.end(),less<int>());
  Print(arr);

cout << "sort with from big to small: " << endl;
  stable_sort(arr.begin(),arr.end(),greater<int>());
  Print(arr);

//自写compare函数排序
cout << "sort with from small to big: " << endl;
  sort(arr.begin(),arr.end(),CompIntLess);
  Print(arr);
cout << "sort with from big to small" << endl;
  sort(arr.begin(),arr.end(),CompIntGreater);
  Print(arr);
}
/**
对数组排序
**/
void SortIntArray()
{
int a[10] = {5, 6, 4, 3, 7, 0 ,8, 9, 2, 1};
cout << "sort with from small to big: " << endl;
  sort(a, a + 10, less<int>());
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
  }
cout << endl;
cout << "sort with from big to small: " << endl;
  sort(a, a + 10, greater<int>());
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
  }
cout << endl;
}

int main(){
   SortInt();
   SortIntArray();
return 0;
}