// sort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "windows.h" // SYSTEMTIME
#include "stdlib.h"  // system调用

#define SIZE 9

typedef struct
{
 int key;
 char name[10];
}Data;

// 0号数据不参与排序，只用作监督哨或者临时变量
Data ListOld[] = {{0, "零号"}, {49, "一号"}, {38, "二号"}, {65, "三号"}, {97, "四号"}, {76, "五号"}, {13, "六号"}, {27, "七号"}, {49, "八号"}};
Data ListNew[SIZE];

void PrintData(Data *pData, int n);
void CopyList(Data *pNew, Data *pOld, int n);
void InsertSort(Data *pData, int n);
void QuickSort(Data *pData, int n);
void BubbleSort(Data *pData, int n);
void SelectSort(Data *pData, int n);

int main(int argc, char* argv[])
{
 int i;
 SYSTEMTIME sys;

 do
 {
  system("cls");
  printf("\t\tC语言数据内部排序！\n\n\t输入对应数字，选择排序方法：\n");
  printf("\t1、插入排序\t\t2、快速排序\n");
  printf("\t3、冒泡排序\t\t4、选择排序\n");
  printf("\t0、退出\n");

  scanf("%d", &i);

  switch( i )
  {
  case 1:
   GetLocalTime(&sys);  // 记录排序开始时间
   printf("%4d/%02d/%02d %02d:%02d:%02d.%03d 星期%1d\n" ,sys.wYear,sys.wMonth,
    sys.wDay,sys.wHour,sys.wMinute,sys.wSecond,sys.wMilliseconds,sys.wDayOfWeek);
   InsertSort(ListOld, SIZE);
   break;
  case 2:
   QuickSort(ListOld, SIZE);
   break;
  case 3:
   BubbleSort(ListOld, SIZE);
   break;
  case 4:
   SelectSort(ListOld, SIZE);
   break;
  default:
   break;
  }
  system("pause");
 }while(i != 0);

 return 0;
}

void PrintData(Data *pData, int n)
{
 int i;
 for(i=1; i<n; i++)
 {
  printf("%d,%s   ", pData[i].key, pData[i].name);
 }
 printf("\n");
}

void CopyList(Data *pNew, Data *pOld, int n)
{
 for(int i=1; i<n; i++)
 {
  pNew[i] = pOld[i];
 }
}

// 插入排序
void InsertSort(Data *pData, int n)
{
 int i, j;

 CopyList(ListNew, pData, n);
 for(i=2; i<n; i++)
 {
  if(ListNew[i].key < ListNew[i-1].key)
  {
   ListNew[0] = ListNew[i];
   for(j=i-1; ListNew[0].key < ListNew[j].key; j--)
   {
    ListNew[j+1] = ListNew[j];
   }
   ListNew[j+1] = ListNew[0];
  }
 }
 printf("InsertSort\n");
 PrintData(ListOld, SIZE);
 PrintData(ListNew, SIZE);
}

// 快速排序
int Partition(Data *pData, int low, int high)
{
 int pivotkey = pData[low].key;
 pData[0] = pData[low];

 while(low < high)
 {
  while(low<high && pData[high].key>=pivotkey)
   high--;
  pData[low] = pData[high];
  while(low<high && pData[low].key<=pivotkey)
   low++;
  pData[high] = pData[low];
 }
 pData[low] = pData[0];

 return low;
}
void QSort(Data *pData, int low, int high)
{
 int pivotloc;

 if(low < high)
 {
  pivotloc = Partition(pData, low, high);
  QSort(pData, low, pivotloc-1);
  QSort(pData, pivotloc+1, high);
 }
}
void QuickSort(Data *pData, int n)
{
 CopyList(ListNew, pData, n);
 QSort(ListNew, 1, n-1);
 printf("QuickSort\n");
 PrintData(ListOld, SIZE);
 PrintData(ListNew, SIZE);
}

//冒泡排序
void BubbleSort(Data *pData, int n)
{
 int i, j, isExchanged;

 CopyList(ListNew, pData, n);
 for(i=1; i<n-1; i++)
 {
  isExchanged = 0;

  for(j=1; j<n-i; j++)
  {
   if(ListNew[j].key > ListNew[j+1].key)
   {
    ListNew[0] = ListNew[j];
    ListNew[j] = ListNew[j+1];
    ListNew[j+1] = ListNew[0];

    isExchanged = 1;
   }
  }

  if( !isExchanged )
   break;
 }

 printf("BubbleSort\n");
 PrintData(ListOld, SIZE);
 PrintData(ListNew, SIZE);
}

// 选择排序
void SelectSort(Data *pData, int n)
{
 int i, j, index;

 CopyList(ListNew, pData, n);
 for(i=1; i<n; i++)
 {
  index = i;
  for(j=i+1; j<n; j++)
  {
   if(ListNew[j].key < ListNew[index].key)
   {
    index = j;
   }
  }

  if(index != i)
  {
   ListNew[0] = ListNew[i];
   ListNew[i] = ListNew[index];
   ListNew[index] = ListNew[0];
  }
 }

 printf("SelectSort\n");
 PrintData(ListOld, SIZE);
 PrintData(ListNew, SIZE);
}