c++实现各种排序算法

#if 1
#include<iostream>
using namespace std;
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  int flag=0;
  for (int i = 1; i < 10; i++)
  {   
    for (int j = 0; j < 10 - i; j++)
      if (t[j] > t[j + 1])
        swap(t[j], t[j + 1]),flag=1;
    if (flag == 0)  break;
    flag == 0;
  }
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
  return 0;
}
#endif

#if 1
#include<iostream>
using namespace std;
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  for (int i = 0; i < 9; i++)
  {
    int min=i;
    for (int j = i + 1; j < 10; j++)
      if (t[min] > t[j])
        min = j;
    swap(t[i], t[min]);
  }
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
  return 0;
}
#endif

#if 1
#include<iostream>
using namespace std;
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  for (int i = 1; i < 9; i++)
  {
    for (int j = i +1; j > 0; j--)
      if (t[j] < t[j-1])
        swap(t[j-1], t[j]);
  }
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
}
#endif

#if 1
#include<iostream>
using namespace std;
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  for (int div = 10 / 2; div >= 1; div /= 2)
    for (int k = 0; k < div; k++)
      for (int i = div + k; i < 10; i += div)
        for (int j = i; j > k; j -= div)
        {
          if (t[j] < t[j - div])
            swap(t[j], t[j - div]);
          else
            break;
        }
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
  return 0;
}
#endif 

#if 1
#include<iostream>
using namespace std;
int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
void quike(int left, int right)
{
  int i = left;
  int j = right;
  int temp = t[left];
  int k;
  if (left >= right) return;
  while (i < j)
  {
    while (i < j && temp <= t[j])
      j--;
    while (i<j && temp>=t[i])
      i++;
    if (i < j)
      k=t[i],t[i]=t[j],t[j]=k;
  }
  if (i == j)
    k = t[left], t[left]=t[i],t[i]=k;
  cout << i << " " << j << endl;
  quike(left, j-1);
  quike(j+1, right);
}
int main()
{
  quike(0, 9);
  for (int i = 0; i < 10; i++)
    cout << t[i] << " " ;
}
#endif

#if 1
#include<iostream>
using namespace std;
void merge(int* a, int l, int mid, int r)
{
  int n1 = mid - l+1;
  int n2 = r - mid;
  int* L = new int[n1+1];
  int* R = new int[n2+1];
  for (int i = 0; i < n1; i++)
    L[i] = a[i + l];
  for (int i = 0; i < n2; i++)
    R[i] = a[mid + 1 + i];
  L[n1] = 11111111;
  R[n2] = 11111111;       //以便下面的归并操作，不然会内存溢出的；
  int i = 0, j = 0;
  int k = l;
  for (; k <=r; k++)
  {
    if (L[i] >= R[j])
      a[k] = R[j++];
    else
      a[k] = L[i++];
  }
  delete[]L;
  delete[]R;
}
void mergesort(int *a, int l, int r)
{
  if (r > l)
  {
    int mid = (l + r) / 2;
    mergesort(a, l, mid);
    mergesort(a, mid + 1, r);
    merge(a, l, mid, r);
  }
}
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  mergesort(t, 0, 9);
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
}
#endif

#if 1
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
  int largest = i;
  int l = i * 2 + 1;
  int r = i * 2 + 2;
  if (l<n && arr[l]>arr[largest])
    largest = l;
  if (r<n&&arr[r]>arr[largest])
    largest = r;
  if (largest != i)
  {
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
  }
}
void heapsort(int arr[], int n)
{
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);
  for (int i = n - 1; i >= 0; i--)
  {
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  heapsort(t, 10);
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
}
#endif

#if 0
#include<iostream>
using namespace std;
int maxbit(int data[], int n)
{
  int d = 1;
  int p = 10;
  for (int i = 0; i < n; i++)
    while (data[i] >= p)
      p *= 10, ++d;
  return d;
}
void base_sort(int a[], int n)
{
  int d = maxbit(a, n);
  int *temp = new int[n];
  int *count = new int[10];
  int i, j, k;
  int radix = 1;
  for (i = 1; i <= d; i++)
  {
    for (j = 0; j < 10; j++)
      count[j] = 0;
    for (j = 0; j < n; j++)
    {
      k = (a[j] / radix) % 10;
      count[k]++;
    }
    for (j = 1; j < 10; j++)
      count[j] = count[j - 1] + count[j];
    for (j = n - 1; j >= 0; j--)
    {
      k = (a[j] / radix) % 10;
      temp[count[k] - 1] = a[j];
      count[k]--;
    }
    for (j = 0; j < n; j++)
      a[j] = temp[j];
    radix = radix * 10;
  }
  delete[]temp;
  delete[]count;
}
int main()
{
  int t[10] = { 2,5,7,3,1,8,6,3,7,0 };
  base_sort(t, 10);
  for (int i = 0; i < 10; i++)
    cout << t[i] << " ";
}
#endif